[프로그래머스] 게임 맵 최단거리 (Java)

[프로그래머스] 게임 맵 최단거리 (Java)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java

풀이/후기

정말정말 오랜만에 DFS/BFS 문제를 풀어봤다.

다행히 다 까먹지는 않았나보다..ㅎ

 

제출하니 효율성 검사에서 모두 시간 초과가 발생했다.

처음에 출력 시 int ans에 대입해서 반환했는데,

그냥 바로 visited[][] 값으로 반환하니 통과할 수 있었다.

 

프로그래머스로 많이 풀어보지 않아 이런 디테일한 채점 시스템이 좀 신기했다.

어디가 틀렸는지 모르니 계속 고민하게 되었다. 그 김에 비효율적인 요소까지 고려할 수 있었다.

 

코드

import java.util.*;

class Solution {

    static Queue<int[]> q = new LinkedList<>();
    static int[][] visited;
    static int[][] dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    static int[][] map;
    static int n, m;
    
    public int solution(int[][] maps) {
        
        n = maps.length;
        m = maps[0].length;
        
        map = maps;
        visited = new int[n][m];
        
        q.add(new int[]{0,0});
        visited[0][0] = 1;
        
        return func();
    }
    
    static int func(){
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            
            
            for (int i=0; i<4; i++){
                int nx = cx + dir[i][0];
                int ny = cy + dir[i][1];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] == 0 && map[nx][ny] != 0 ){
                    // 범위 내에 있다면
                    q.add(new int[]{nx, ny});
                    visited[nx][ny] = visited[cx][cy] + 1;
                }
            }
        }
        
        if (visited[n-1][m-1] == 0){
            return -1;
        }
        else 
            return visited[n-1][m-1];
    }
}

Commit

 

참고