[BOJ/Java] 3197. 백조의 호수

[BOJ/Java] 3197. 백조의 호수

https://www.acmicpc.net/problem/3197

---

문제 해석

백조의 호수 문제는 두 마리의 백조가 있는 호수에서 얼음이 녹아 백조들이 만날 수 있는 최소 시간을 구하는 문제이다. 호수는 2차원 격자로 표현되며, 각 칸은 물('.') 또는 얼음('X')으로 구성된다. 백조는 물 위에서만 이동할 수 있으며, 매일 얼음이 물과 인접한 부분부터 녹는다. 두 백조가 만날 수 있는 최소 일수를 계산해야 한다.

풀이 과정

1. 초기 설정: 호수의 상태를 입력받고, 두 백조의 위치를 찾는다. 또한, 얼음이 녹는 과정을 시뮬레이션하기 위해 BFS를 사용한다.
2. 얼음 녹이기: 물과 인접한 얼음을 녹이는 과정을 BFS로 구현한다. 이때, 얼음이 녹는 순서를 큐에 저장하여 매일 얼음이 녹는 과정을 시뮬레이션한다.
3. 백조 만남 확인: 두 백조가 같은 물 영역에 속하는지 확인하기 위해 BFS를 사용한다. 매일 얼음이 녹은 후, 두 백조가 연결되는지 확인한다.
4. 최소 일수 계산: 얼음이 녹는 과정과 백조의 연결 여부를 반복하여 두 백조가 만나는 최소 일수를 계산한다.

코드

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

public class Main {
    static int R, C;
    static char[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Queue<int[]> waterQueue = new LinkedList<>(); // 제네릭 타입 명시
    static Queue<int[]> swanQueue = new LinkedList<>(); // 제네릭 타입 명시
    static boolean[][] visited;
    static int[] swanPos = new int[4]; // 두 백조의 위치 저장

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

        map = new char[R][C];
        visited = new boolean[R][C];

        int swanIdx = 0;
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'L') {
                    swanPos[swanIdx++] = i;
                    swanPos[swanIdx++] = j;
                }
                if (map[i][j] == '.' || map[i][j] == 'L') {
                    waterQueue.add(new int[]{i, j});
                }
            }
        }

        // 백조의 시작 위치 설정
        swanQueue.add(new int[]{swanPos[0], swanPos[1]});
        visited[swanPos[0]][swanPos[1]] = true;

        int day = 0;
        while (true) {
            if (canMeet()) {
                System.out.println(day);
                break;
            }
            meltIce();
            day++;
        }
    }

    // 백조가 만날 수 있는지 확인
    static boolean canMeet() {
        Queue<int[]> nextQueue = new LinkedList<>(); // 제네릭 타입 명시
        while (!swanQueue.isEmpty()) {
            int[] current = swanQueue.poll(); // 이제 int[]로 캐스팅됨
            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                if (nx >= 0 && nx < R && ny >= 0 && ny < C && !visited[nx][ny]) {
                    if (nx == swanPos[2] && ny == swanPos[3]) {
                        return true;
                    }
                    if (map[nx][ny] == '.') {
                        visited[nx][ny] = true;
                        swanQueue.add(new int[]{nx, ny});
                    } else if (map[nx][ny] == 'X') {
                        visited[nx][ny] = true;
                        nextQueue.add(new int[]{nx, ny});
                    }
                }
            }
        }
        swanQueue = nextQueue;
        return false;
    }

    // 얼음 녹이기
    static void meltIce() {
        int size = waterQueue.size();
        for (int i = 0; i < size; i++) {
            int[] current = waterQueue.poll(); // 이제 int[]로 캐스팅됨
            for (int j = 0; j < 4; j++) {
                int nx = current[0] + dx[j];
                int ny = current[1] + dy[j];
                if (nx >= 0 && nx < R && ny >= 0 && ny < C && map[nx][ny] == 'X') {
                    map[nx][ny] = '.';
                    waterQueue.add(new int[]{nx, ny});
                }
            }
        }
    }
}

시간 복잡도 분석

시간 복잡도는 O(R * C)이다. 호수의 모든 칸을 탐색하며 얼음을 녹이고, 백조가 만날 수 있는지 확인하는 과정이 각각 BFS로 구현되기 때문이다. 이는 문제의 제약 조건 내에서 효율적으로 동작한다.

느낀점

이 문제는 BFS를 활용하여 얼음이 녹는 과정과 백조의 이동을 동시에 시뮬레이션하는 문제이다. 얼음이 녹는 과정을 효율적으로 처리하기 위해 큐를 사용한 점이 핵심이었다. 또한, 백조가 만날 수 있는지 확인하는 과정에서도 BFS를 사용하여 문제를 해결할 수 있었다. 그래프 탐색과 시뮬레이션을 결합한 문제로, 실시간으로 변화하는 환경을 다루는 능력을 키울 수 있는 좋은 문제였다.