백준 2589번
https://www.acmicpc.net/problem/2589

문제

---

생각하기

---

• BFS 문제

  • 문제에 최단 거리로 이동하는 시간을 구하라고 나옴

• 문제를 잘 생각해야됨,

  • 처음 문제에서 '보물은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다' 라고 문제에 나와있어서 보물이 묻힌 곳을 먼저 구해야 하는 줄 알았다.
  • 근데 BFS를 각 좌표에서 출발하여 완전탐색을 통해 구해진 시간 중 최댓값을 구하면 그게 정답이였음

동작

        int shortestTime = -1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 'L') {
                    shortestTime = Math.max(BFS(i, j), shortestTime);
                }
            }
        }

arr에서 육지 부분일 경우, 모두 출발점으로 삼아서 육지부분을 전체 탐색한다.

쉽게 말해서 각 지점에서 모두 출발하고, 갈 수 있는 경로 끝 까지 가면서 최대시간을 구하는 것이다.
그리고 이 시간들 중 최대값을 구하면 된다.

            for (int i = 0; i < 4; i++) {
                int nowX = m.x + dirX[i];
                int nowY = m.y + dirY[i];
                int currentTime = m.time;

                if (rangeCheck(nowX, nowY) && !visit[nowX][nowY] && arr[nowX][nowY] == 'L') {
                    visit[nowX][nowY] = true;
                    que.offer(new Map(nowX, nowY, currentTime + 1));
                    time = Math.max(currentTime + 1, time);
                }

            }

방문을 하면서, 시간을 1씩 늘려가면서 최대값을 갱신하는 방향으로 나아간다.

코드

---

Java

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

public class Main {
    static int[] dirX = {0, 0, -1, 1};
    static int[] dirY = {1, -1, 0, 0};
    static char[][] arr;
    static int N, M;

    static class Map {
        int x;
        int y;
        int time;

        public Map(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    } // End of Map class

    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());
        arr = new char[N][M];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = str.charAt(j);
            }
        }

        int shortestTime = -1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 'L') {
                    shortestTime = Math.max(BFS(i, j), shortestTime);
                }
            }
        }

        System.out.println(shortestTime);
    } // End of main

    private static int BFS(int x, int y) {
        Queue<Map> que = new LinkedList<>();
        boolean[][] visit = new boolean[N][M];
        int time = 0;
        
        visit[x][y] = true;
        que.offer(new Map(x, y, 0));

        while (!que.isEmpty()) {
            Map m = que.poll();

            for (int i = 0; i < 4; i++) {
                int nowX = m.x + dirX[i];
                int nowY = m.y + dirY[i];
                int currentTime = m.time;

                if (rangeCheck(nowX, nowY) && !visit[nowX][nowY] && arr[nowX][nowY] == 'L') {
                    visit[nowX][nowY] = true;
                    que.offer(new Map(nowX, nowY, currentTime + 1));
                    time = Math.max(currentTime + 1, time);
                }

            }
        }

        return time;
    } // End of BFS

    private static boolean rangeCheck(int nowX, int nowY) {
        return nowX >= 0 && nowX < N && nowY >= 0 && nowY < M;
    } // End of rangeCheck
} // End of Main class