백준 2589(JAVA)

문제

보드위에는 육지와 바다가있는데 육지에서 육지로만 갈수있고 현재위치에서 상하좌우 밖에움직이지 못한다. 이 보드위에 보물이 두군데 묻혀있는데 보물은 최단거리중 가장 긴 시간이 걸리는 곳에 묻혀있다. 보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

풀이

최단거리리라는 것이 무엇인지 문제에 주어져있다.
이 문제를 보고 bfs로 바로 풀어야겠다는 생각이 난들었다. (가중치없는 최단거리이동은 bfs이다.)
bfs가 어떤식으로 그래프를 탐색하는지 생각하면 어렵지않게 생각할수있는 문제이다.

보드의 각 위치를 모두 탐색하면서 해당 위치에서 가장 긴시간이 걸리는 육지칸을 찾은 다음, 이 시간과 static 변수인 max중 큰 값을 비교하며 최신화하며 풀었다. 탐색한뒤 visited와, board는 계속 초기화되어야하기에 초기화하는 메서드가 존재한다.
(그래프탐색 어렵지않은 문제이다.)

코드

package baekjoon.그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main2589 {
    static int N, M;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int max = -1;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < M; j++){
                board[i][j] = str.charAt(j) == 'W' ? 0 : 1; //바다는 0 육지는 1
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                int[][] newBoard = init();
                max = Math.max(max, bfs(i, j, newBoard));
            }
        }
        System.out.println(max - 1);

    }
    static int bfs(int x, int y, int[][] board){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        int maxV = -1;
        visited[x][y] = true;

        while(!q.isEmpty()){
            int[] poll = q.poll();
            int c1 = poll[0];
            int c2 = poll[1];
            for(int i = 0; i < 4; i++){
                int nextX = c1 + dx[i];
                int nextY = c2 + dy[i];
                if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
                if(board[nextX][nextY] == 0) continue;
                if(visited[nextX][nextY]) continue;
                q.offer(new int[]{nextX, nextY});
                visited[nextX][nextY] = true;
                board[nextX][nextY] = board[c1][c2] + 1;
                maxV = Math.max(maxV, board[nextX][nextY]);
            }
        }
        return maxV;
    }
    static int[][] init(){
        int[][] newBoard = new int[N][M];

        for (boolean[] booleans : visited) {
            Arrays.fill(booleans, false);
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                newBoard[i][j] = board[i][j];
            }
        }
        return newBoard;
    }
}