3197번: 백조의 호수

문제

두 마리의 백조가 호수에 살고 있습니다. 호수는 행 R, 열 C 크기의 직사각형 모양이며, 물('.')과 빙판('X'), 그리고 백조('L')로 이루어져 있습니다. 매일 빙판은 물과 닿아있는 부분이 녹아서 물로 변합니다. 백조는 오직 물을 따라서 상하좌우로만 이동할 수 있습니다. 며칠이 지나야 두 백조가 서로 만날 수 있는지 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 R과 C가 주어집니다. (1 ≤ R, C ≤ 1,500) 둘째 줄부터 R개의 줄에 호수의 상태가 주어집니다.
• 출력: 첫째 줄에 며칠이 지나야 두 백조가 만날 수 있는지 출력합니다.

풀이: 2개의 큐(Queue)를 활용한 이어 달리기 BFS 최적화

이 문제의 맵 최대 크기는 1,500 × 1,500입니다. 만약 매일 얼음을 녹이고, 백조가 만날 수 있는지 매번 출발점부터 새로 BFS를 수행한다면 시간 초과가 발생합니다. 이를 해결하기 위해 물과 백조의 탐색 상태를 기억해 두고, 다음 날에는 이전 날에 막혔던 지점(빙판)부터 이어서 탐색하는 방식을 사용해야 합니다.

• 초기화 과정:
  • 입력을 받으며 빙판이 아닌 곳(물 .과 백조 L)의 위치는 모두 얼음을 녹이는 주체가 되므로 waterQ에 넣습니다.
  • 백조(L)를 만났을 때, 두 마리의 백조 중 첫 번째 백조만 출발점으로 삼기 위해 swanQ.isEmpty() 조건을 확인하고 큐(swanQ)에 삽입 및 방문 처리(visited)를 마칩니다.
• 백조 이동 (check 메서드):
  • swanQ에는 현재 물이라서 이동 가능한 경로들이 들어있습니다. 이 경로들을 탐색하며 상하좌우로 이동합니다.
  • 핵심 로직: 이동할 다음 칸이 물이면 계속해서 swanQ에 넣고 탐색하지만, 빙판('X')을 만나면 내일 녹을 예정이므로 nextSwanQ에 보관해 둡니다. 그리고 방문 처리를 하여 중복 탐색을 막습니다.
  • 다른 백조('L')를 만나면 즉시 true를 반환합니다.
• 얼음 녹이기 (melt 메서드):
  • waterQ에 들어있는 물의 위치에서 상하좌우를 탐색합니다.
  • 인접한 칸에 빙판('X')이 있다면 녹는 표시로 바꾸고, 내일 이 자리 주변의 빙판이 또 녹아야 하므로 해당 위치를 nextWaterQ에 넣어둡니다.
• 상태 전이:
  • 하루의 시뮬레이션이 끝난 뒤, 백조와 물의 탐색 큐를 다음 날 탐색해야 할 큐(nextSwanQ, nextWaterQ)로 교체합니다. 이를 통해 O(R * C) 시간 복잡도로 빠르게 정답을 찾을 수 있습니다.

코드

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

public class Main {
    static class Node {
       int y, x;

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

    static int n, m;
    static char[][] a;
    static boolean[][] visited;

    static Queue<Node> waterQ = new LinkedList<>();
    static Queue<Node> swanQ = new LinkedList<>();
    static Queue<Node> nextWaterQ;
    static Queue<Node> nextSwanQ;

    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];
       visited = new boolean[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);

             // 물이거나 백조인 경우(즉, 빙판이 아닌 경우) 얼음을 녹이기 위해 waterQ에 추가
             if (a[i][j] != 'X') {
                waterQ.add(new Node(i, j));
             }

             // 두 마리의 백조 중 첫 번째로 발견된 백조만 탐색 시작점으로 큐에 삽입
             if (a[i][j] == 'L' && swanQ.isEmpty()) {
                swanQ.add(new Node(i, j));
                visited[i][j] = true;
             }
          }
       }

       int ans = 0;
       while (true) {
          nextWaterQ = new LinkedList<>();
          nextSwanQ = new LinkedList<>();

          // 백조가 서로 만났는지 확인
          if (check()) {
             break;
          }

          // 얼음 녹이기
          melt();

          // 큐 교체 (내일의 탐색을 위해)
          swanQ = nextSwanQ;
          waterQ = nextWaterQ;
          ans++;
       }

       bw.write(ans + "");

       bw.flush();
    }

    // 백조가 물을 따라 이동하는 BFS 탐색
    static boolean check() {
       while (!swanQ.isEmpty()) {
          Node node = swanQ.poll();
          for (int i = 0; i < 4; i++) {
             int ny = node.y + dy[i];
             int nx = node.x + dx[i];

             if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx])
                continue;

             // 다른 백조를 만난 경우 탐색 종료
             if (a[ny][nx] == 'L') {
                return true;
             }
             // 빙판을 만난 경우 내일 탐색하기 위해 nextSwanQ에 추가
             else if (a[ny][nx] == 'X') {
                nextSwanQ.add(new Node(ny, nx));
             }
             // 물인 경우 계속 이동 가능하므로 swanQ에 추가
             else {
                swanQ.add(new Node(ny, nx));
             }

             visited[ny][nx] = true;
          }
       }

       return false;
    }

    // 물과 인접한 빙판을 녹이는 BFS 탐색
    static void melt() {
       while (!waterQ.isEmpty()) {
          Node node = waterQ.poll();
          for (int i = 0; i < 4; i++) {
             int ny = node.y + dy[i];
             int nx = node.x + dx[i];

             if (ny < 0 || nx < 0 || ny >= n || nx >= m) {
                continue;
             }

             // 인접한 칸이 빙판이면 물로 바꾸고 내일 탐색할 waterQ에 추가
             if (a[ny][nx] == 'X') {
                a[ny][nx] = '*';
                nextWaterQ.add(new Node(ny, nx));
             }
          }
       }
    }
}

알고리즘 분류

그래프 이론 (Graph Theory), 그래프 탐색 (Graph Traversal), 너비 우선 탐색 (BFS)