게임 맵 최단거리 - 프로그래머스 (Java, Level 2)

처음 풀이

 

보자마자 dfs가 먼저 떠올랐다. 

이동할 때마다 isOkToGo()로 범위, 방문 여부, 벽을 확인한다.

목적지에 도착하면 최솟값을 갱신한다.

 

boolean[][] isVisited
int min = Integer.MAX_VALUE;

public int solution(int[][] maps) {
    isVisited = new boolean[maps.length][maps[0].length];
    dfs(0, 0, maps, 1);
    //한 번도 갱신이 안되었으면 목적지에 도착하지 못한 것이니 -1리턴
    return (min==Integer.MAX_VALUE)? -1 : min;
}//solution() end

public void dfs(int y, int x, int[][] maps, int count) {

    isVisited[y][x] = true;

    if(y==maps.length-1 && x==maps[0].length-1) {
        //목적지 도착 -> 최솟값 갱신
        min = Math.min(min, count);
        return;
    }

    //right
    if(isOkToGo(y, x+1, maps)) {
        dfs(y, x+1, maps, count+1);
    }
    //down
    if(isOkToGo(y+1, x, maps)) {
        dfs(y+1, x, maps, count+1);
    }
    //left
    if(isOkToGo(y, x-1, maps)) {
        dfs(y, x-1, maps, count+1);
    }
    //up
    if(isOkToGo(y-1, x, maps)) {
        dfs(y-1, x, maps, count+1);
    }

    //모든 방향 try 후 현재 위치 false로 초기화
    isVisited[y][x] = false;
}//dfs() end

//이동 시 벽, 범위, 방문여부 확인하는 method
public boolean isOkToGo(int y, int x, int[][] maps) {
    return !(y > maps.length-1 || y<0
            || x > maps[0].length-1 || x<0
            || maps[y][x]==0
            || isVisited[y][x]);
}//isOkToGo() end

 

 

결과를 보면 정확성은 전부 통과했지만, 효율성에서 통과하지 못했다.

아마 재귀함수 때문에 모든 위치에서 모든 방향으로 이동하면서 함수를 호출해서 그런 것이라 생각했다.

 

 

다른 풀이

dfs가 아닌 bfs 방식으로 많이 풀었다.

 

int[] dy = {1, 0, -1, 0}, dx = {0, 1, 0, -1};
boolean[][] isVisited;

class Point {
    int y;
    int x;
    int distance;

    Point(int y, int x, int distance) {
        this.y = y;
        this.x = x;
        this.distance = distance;
    }
}

//bfs 풀이
public int solution2(int[][] maps) {
    int rows = maps.length;
    int columns = maps[0].length;

    isVisited = new boolean[rows][columns];

    Queue<Point> queue = new LinkedList<>();

    queue.add(new Point(0, 0, 1));
    isVisited[0][0] = true;

    while(!queue.isEmpty()) {
        Point point = queue.poll();
        if(point.y==rows-1 && point.x==columns-1) return point.distance;

        for(int i=0; i<4; i++) {
            int ny = point.y + dy[i];
            int nx = point.x + dx[i];

            if(isOkToGo(ny, nx, maps)) {
                isVisited[ny][nx] = true;
                queue.add(new Point(ny, nx, point.distance+1));
            }
        }//for end
    }//while end

    return -1;

}//solution2() end

//이동 시 벽, 범위, 방문여부 확인하는 method
public boolean isOkToGo(int y, int x, int[][] maps) {
    return !(y > maps.length-1 || y<0
            || x > maps[0].length-1 || x<0
            || maps[y][x]==0
            || isVisited[y][x]);
}//isOkToGo() end

 

 

효율성까지 통과했다.