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

 

BFS

최단 경로를 찾는 문제에서는 도착점에 도달한 순간 종료되는 BFS를 이용한다. DFS는 모든 경로를 탐색하기 때문에 적합하지 않다.

[그래프 탐색] BFS / DFS

[그래프 탐색] BFS / DFS

 

전체 풀이

import java.util.*;

class Solution {
    
    // 상하좌우 이동할 수 있는 좌표
    int[] dx = {0, 1, -1, 0};
    int[] dy = {1, 0, 0, -1};
    
    public int solution(int[][] maps) {
        
        int answer = 0;

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

        bfs(maps, visited);
        answer = visited[maps.length - 1][maps[0].length - 1]; // 상대 팀 진영 좌표

        if (answer == 0) { // 상대 팀 진영에 도달하지 못한 경우
            answer = -1;
        }

        return answer;
    }
    
    public void bfs(int[][] maps, int[][] visited) {

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0}); // Queue에 시작 정점 추가
        visited[0][0] = 1;

        while (!q.isEmpty()) { // 더 나아갈 정점이 없을 때까지 반복

            int[] current = q.poll(); // 정점 하나 꺼내기
            int X = current[0];
            int Y = current[1];

            for (int i = 0; i < 4; i++) {

                int nX = X + dx[i];
                int nY = Y + dy[i];

                // 좌표가 maps에서 벗어날 경우 다음 반복으로 넘어간다
                if (nX < 0 || nX > maps.length - 1 || nY < 0 || nY > maps[0].length - 1) {
                    continue;
                }

                // 아직 방문하지 않았고, 벽이 아닐 경우
                if (visited[nX][nY] == 0 && maps[nX][nY] == 1) {
                    visited[nX][nY] = visited[X][Y] + 1;
                    q.add(new int[]{nX, nY});
                }
            }
        }
    }
}

 

bfs 메서드

• 경로를 담을 Queue를 생성한다. 시작 위치인 (0, 0)을 담고 방문을 체크하는 배열 visited[0][0]에 1을 담는다.
• while문은 더 나아갈 경로가 없거나 Queue가 비어 있게 될 때 반복이 끝난다.
  • Queue에 담긴 경로인 정점 하나를 꺼내고 변수 X와 Y에 각각 X좌표와 Y좌표를 담는다.
  • 변수 nX와 nY는 상하좌우로 나아갈 수 있는 좌표이다.
  • 좌표가 maps에서 벗어날 경우에는 다음 반복으로 넘어간다.
  • 만약 아직 방문하지 않은 경로이고, 벽이 아니라면 경우의 수를 누적시킨다.
  • Queue에 새로운 좌표를 넣는다.