BFS 최단 경로 구하기

백준 17086번을 BFS를 이용해 Java로 풀어봤다.
이번 문제 역시 허무하게 끝났다.... 나의 멍청함에 감탄을 금할 수 없다 ㅎ

이번 문제는 bfs()를 한 번만 돌려주면 되는 것이 아니라 각 좌표마다 값이 0이면 돌려줘야 하는데 문제였다. 따라서 매번 bfs()를 실행할 때마다 visited 배열을 새롭게 초기화해줘야 하는데 main 함수에서 한 번 초기화해주고 계속해서 어디가 틀린 건지 1시간을 쳐다봤다. 깨닫고 난 후 쌍욕이 절로 나왔다. ㅆ..ㅂ...

이번 문제의 로직은 아주 간단하다. 각 좌표마다 값이 1인 좌표까지의 최소거리를 쭉 구한 후에, 모든 거리 중 최댓값을 도출하면 된다. 최단 경로를 구하는 문제기 때문에 BFS로 간단하게 해결 가능하다.
다만 이미 언급했듯이, bfs()를 여러 번 돌리는 것이기 때문에 매번 visited 정보를 초기화해주는 것만 신경써주면 된다.

이미 이와 같은 유형을 앞서 여러 번 풀어보았기 때문에 더 자세한 설명은 생략하고 제출한 코드로 마친다.

import java.util.*;
import java.io.*;

public class boj17086 {
    static int N, M, answer = -1;
    static int[][] map;
    static boolean[][] visited;
    static int[][] move = new int[][]{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}; // 이동 방향 배열

    static int bfs(int row, int col) {
        visited = new boolean[N + 1][M + 1]; // 아.... 매 좌표마다 bfs() 돌려주니까 매번 boolean 배열 새로 초기화해야 하는데,,, main에서 한 번 하고 말았다...
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{row, col, 0});
        visited[row][col] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int j = 0; j < 8; j++) { // 방향별로 움직여주자
                int newRow = cur[0] + move[j][0];
                int newCol = cur[1] + move[j][1];
                int newDist = cur[2] + 1;

                if (newRow < 0 || newRow >= N || newCol < 0 || newCol >= M || visited[newRow][newCol])
                    continue;

                if (map[newRow][newCol] == 1)
                    return newDist;
                q.add(new int[]{newRow, newCol, newDist});
                visited[newRow][newCol] = true;
            }
        }
        return 0;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        map = new int[N + 1][M + 1];

        for (int i = 0; i < N; i++) {
            stk = new StringTokenizer(bfr.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1)
                    continue;
                int tmp = bfs(i, j);
                answer = tmp > answer ? tmp : answer;
            }
        }
        System.out.println(answer);
    }
}

오늘 배운 것

bfs() 를 여러 번 실행할 때는 반드시 매번 visited 배열을 초기화해주자