LV2. 게임 맵 최단거리

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

풀이

가장 기본적인 BFS 문제이다.

 

다만 다른점이라면 목표한 지점에 도달했을 때, 최단거리를 구해야 한다는 것이다.

 

이 부분은 이전에 거쳐왔던 곳에서 +1을 해가면서 갈 수 있는 모든 곳의 거리를 구하면 끝난다

 

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

private static int solution(int[][] maps) {
    int answer = 0;

    int[][] visit = new int[maps.length][maps[0].length];

    Queue<Node> q = new LinkedList<>();
    visit[0][0] = 1;

    q.add(new Node(0, 0));

    while (!q.isEmpty()) {
        Node now = q.poll();

        for (int i = 0; i < 4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if (nx >= 0 && ny >= 0 && ny < maps.length && nx < maps[0].length && maps[ny][nx] != 0 && visit[ny][nx] == 0) {
                q.add(new Node(nx, ny));
                visit[ny][nx] = visit[now.y][now.x] + 1;
            }
        }
    }

    answer = visit[maps.length - 1][maps[0].length - 1] == 0 ? -1 : visit[maps.length - 1][maps[0].length - 1];

    return answer;
}

static class Node {
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

위 코드와 같이 앞으로 갈 지점을 nx, ny로 표현한 뒤 4방향을 탐색하기 시작한다.

 

조건문에서는 이미 방문하였는지와 벽으로 막힌 곳이 아닌지를 판별하며 탐색하면 된다.

 

만일 길에 막혀 목표 지점을 못 가는 경우도 있을텐데, 그 경우는 목표지점[n-1,m-1]의 visit 여부를 확인하면 된다.

 

아무도 그 지점에 도달하지 못하였으면 visit의 값이 초기값인 0으로 설정되어 있을 것이다. 그게 아니라면 visit의 값을 반환하면 정답이다.