[백준 2589] 보물섬(Java)

문제 링크 : https://www.acmicpc.net/problem/2589

이 문제는 bfs를 이용하여 풀 수 있습니다. 처음에 이 문제를 풀기 위해 첫 번째 보물의 위치와 두 번째 보물의 위치 모두 반복문으로 탐색해서 풀었는데 4중 for문 내에 bfs 코드가 동작하니 시간 초과가 나왔습니다. 따라서 이 문제는 조금 더 생각해서 풀어야 합니다.

가장 핵심적인 부분은 첫 번째 보물의 위치를 알면 두 번째 보물의 위치는 정해진다는 것입니다. 문제에서 두 보물은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 곳에 묻혀있습니다. 따라서 첫 번째 보물의 위치에서 가장 멀리 떨어진 위치가 바로 두 번째 보물이 묻혀 있는 위치입니다. 이 방식으로 반복문 수를 줄여 bfs로 결과를 출력하시면 되겠습니다.

다음은 코드입니다.

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

public class Main{
    static int N,M;
    static int res = 0;
    static boolean[][] req = new boolean[51][51];
    static boolean[][] check = new boolean[51][51];
    static int[] dy = {1,0,-1,0};
    static int[] dx = {0,1,0,-1};

    static void bfs(int i, int j){
        check[i][j] = true;
        Queue<Treasure> queue = new LinkedList<>();
        queue.add(new Treasure(i,j,0));

        // 첫 번째 보물 위치만 움직여서 결과 출력
        while(!queue.isEmpty()){
            Treasure curr = queue.poll();
            int y = curr.y;
            int x = curr.x;
            int cnt = curr.cnt;

            // 만약 첫 번째 보물이 두 번째 보물 위치까지 도달했다면 max와 최댓값 비교
            if(res < cnt) res = cnt;

            // 첫 번째 보물 위치 이동
            for(int dir=0;dir<4;dir++){
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if(ny<0 || ny>=N || nx<0 || nx>=M) continue;

                // 지나간 경로가 아니고 현재 위치가 땅이라면 큐에 cnt 증가시켜 저장
                if(!check[ny][nx] && req[ny][nx]){
                    check[ny][nx] = true;
                    queue.add(new Treasure(ny,nx,cnt+1));
                }
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for(int j=0;j<M;j++){
                req[i][j] = str.charAt(j) != 'W';
            }
        }

        // 첫 번째 보물 위치에 대응하는 두 번째 보물 위치는 정해져 있음
        // 따라서 첫 번째 보물만 bfs로 탐색
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                check = new boolean[51][51];
                if(req[i][j]){
                    bfs(i,j);
                }
            }
        }
        System.out.println(res);
    }
}

class Treasure{
    int y;
    int x;
    int cnt;

    Treasure(int y, int x, int cnt){
        this.y = y;
        this.x = x;
        this.cnt = cnt;
    }
}