2589번: 보물섬

문제

보물섬 지도를 나타내는 N×M 크기의 직사각형 격자가 주어집니다. 각 칸은 육지(L)나 바다(W)로 표시되어 있습니다. 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는 데 1시간이 걸립니다. 보물은 서로 간에 최단 거리로 이동하는 데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀 있습니다. 보물이 묻혀 있는 두 곳 간의 최단 거리 이동 시간을 구하는 문제입니다.

• 입력: 첫째 줄에 보물섬 지도의 세로 크기 N과 가로 크기 M이 주어집니다. 이어 N개의 줄에 걸쳐 보물섬 지도가 주어집니다.
• 출력: 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력합니다.

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

풀이: 모든 육지에서 시작하는 BFS 탐색

보물이 묻혀 있는 두 곳이 어디인지 미리 알 수 없으므로, 모든 육지를 한 번씩 출발점으로 삼아 BFS(너비 우선 탐색)를 수행하여 가장 먼 거리를 구하는 완전탐색 방식을 사용해야 합니다.

1. 육지 좌표 저장: 입력을 받을 때 육지('L')인 칸의 좌표를 미리 List<Node> land에 모아둡니다. 이렇게 하면 지도의 모든 칸을 매번 순회하지 않고, 육지 좌표만 꺼내어 빠르게 출발점으로 설정할 수 있습니다.
2. 완전탐색 (BFS): land 리스트에 담긴 모든 육지를 하나씩 출발점으로 하여 bfs() 메서드를 호출합니다.
   • BFS 큐(Queue)에 시작 노드를 넣고 방문 처리를 합니다. 이때, 거리 계산의 편의와 초기 방문 판별을 위해 시작점의 visited 값을 1로 설정합니다.
   • 큐에서 꺼낸 노드의 상하좌우를 탐색하며, 바다('W')가 아니고 아직 방문하지 않은 육지(visited == 0)라면 큐에 넣고 이전 거리 + 1을 기록합니다.
3. 최대 거리(보물 위치) 갱신: BFS 탐색이 끝난 후 방문 배열을 다시 순회할 필요 없이, 큐에 새로운 좌표를 넣을 때마다 maxD = Math.max(maxD, visited[ny][nx])를 수행하면 해당 탐색에서 도달한 가장 먼 거리를 즉시 알아낼 수 있어 실행 속도가 최적화됩니다. 해당 탐색이 끝나면 구해진 maxD를 전체 최댓값(ans)과 비교하여 갱신합니다.
4. 결과 보정 및 출력: 시작점의 visited 값을 0이 아닌 1로 시작했기 때문에, 최종적으로 구한 최장 거리(ans)에서 1을 뺀 값을 출력해야 정확한 이동 시간이 됩니다.

코드

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

public class Main {
    static int n, m, ans = 0;
    static char[][] a;
    static List<Node> land = new ArrayList<>();
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       n = Integer.parseInt(st.nextToken());
       m = Integer.parseInt(st.nextToken());

       // 지도 정보 입력 및 육지 좌표 수집
       a = new char[n][m];
       for (int i = 0; i < n; i++) {
          String s = br.readLine();
          for (int j = 0; j < m; j++) {
             a[i][j] = s.charAt(j);
             if (a[i][j] == 'L') {
                land.add(new Node(i, j));
             }
          }
       }

       // 모든 육지에서 BFS 탐색 시작
       for (Node node : land) {
          bfs(node);
       }

       // 시작 위치의 거리를 1로 설정했으므로 최종 결과에서 1을 차감
       bw.write((ans - 1) + "");

       bw.flush();
    }

    static void bfs(Node node) {
       Queue<Node> q = new LinkedList<>();
       int[][] visited = new int[n][m];
       
       q.add(node);
       visited[node.y][node.x] = 1; // 시작점 방문 처리

       int maxD = 1; // 현재 탐색의 최대 거리를 기록
       
       while (!q.isEmpty()) {
          Node cur = q.poll();
          
          for (int i = 0; i < 4; i++) {
             int ny = cur.y + dy[i];
             int nx = cur.x + dx[i];
             
             // 지도 범위를 벗어나는지 확인
             if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
             // 바다(W)이거나 이미 방문한 곳이면 이동 불가
             if (a[ny][nx] == 'W' || visited[ny][nx] != 0)
                continue;
             
             q.add(new Node(ny, nx));
             visited[ny][nx] = visited[cur.y][cur.x] + 1; // 거리 증가
             
             maxD = Math.max(maxD, visited[ny][nx]);
          }
       }

       // 전체 탐색 중 최장 거리 갱신
       ans = Math.max(ans, maxD);
    }

    static class Node {
       int y, x;

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

알고리즘 분류

그래프 탐색, 너비 우선 탐색 (BFS), 브루트포스 알고리즘 (완전탐색)