백준 - 쉬운 최단거리

코드

public class Main {
    static int[] nx = new int[]{1, 0, -1, 0};
    static int[] ny = new int[]{0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        boolean[][] visited = new boolean[n][m];
        int[][] map = new int[n][m];
        int sx = 0;
        int sy = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2) {
                    sy = i;
                    sx = j;
                } else if (map[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }

        int[][] answer = new int[n][m];

        visited[sy][sx] = true;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sx, sy});
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();

            for (int i = 0; i < 4; i++) {
                int ex = nx[i] + poll[0];
                int ey = ny[i] + poll[1];
                if (ex >= 0 && ex < m && ey >= 0 && ey < n && !visited[ey][ex]) {
                    answer[ey][ex] = answer[poll[1]][poll[0]]+1;
                    queue.offer(new int[]{ex,ey});
                    visited[ey][ex] = true;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(visited[i][j] ? answer[i][j] : -1).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

풀이

🫡전형적인 BFS 문제입니다.

1. visited[]를 통해 해당 위치에 방문했는지를 파악해줍니다. 0의 경우에도 true로 설정해주었습니다.
2. Queue를 이용하여 bfs를 구현하였습니다. 다음 위치에 갈 수 있다면 [다음 위치] = [현재 위치] + 1로 설정해주었습니다.
3. 정답값을 출력할 경우 해당 visited[]가 false인 경우는 아예 차단 되어서 가지 못한 경우이니 -1을 넣어줍니다. 그 외에는 위에서 저장한 값을 출력해줍니다.

추가 테스트케이스

3 4
2 1 1 1
1 0 0 0
0 1 1 1

를 넣을 경우 아래와 같이 나와야 합니다.

0 1 2 3
1 0 0 0
0 -1 -1 -1

출처 : 백준 - 14940번