[BOJ/BFS] 백준 3197 - 백조의 호수 (Java)

3197 - 백조의 호수

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

문제

두 마리 백조 호수에 살고 있지만 호수를 덮고 있는 빙판으로 만나지 못함
호수 행 R개, 열 C개인 직사각형 모양/ 어떤 칸 얼음으로 덮여있음
호수 차례대로 녹는데 매일 물 공간과 접촉한 모든 빙판 공간 녹음
-> 두 개 공간 접촉하려면 가로 or 세로 닿아 있는 것만(대각선 X) 생각
백조는 물 공간에서 가로 or 세로(대각선 X) 이동 O
=> 며칠 지나야 백조들이 만날 수 있는지

입력
첫째 줄: R, C (1 <= R, C <= 1500)
다음 R개 줄: 각각 길이 C의 문자열 주어짐('.' 물 공간 / 'X' 빙판 공간 / 'L' 백조가 있는 공간)
출력: 주어진 걸리는 날

---

풀이

이중 BFS

• 백조 이동(`moveSwan()`)
  • 백조 물(`.`) 위로만 이동
  • 얼음(`X`) 못가지만 내일 녹을 가능성 O -> 다음 큐에 저장
• 얼음 녹이기(`melt()`)
  • 물(`.`) 주변의 얼음 녹임
  • 녹은 칸(`X`)은 내일의 물(`nextWaterQ`)로 이동

=> 매일 반복

int day = 0;
while (true) {
    if (moveSwan()) {
        System.out.println(day);
        return;
    }
    melt();
    day++;
}

 

입력

• `map[i][j] != 'X'`: 현재 얼음 X = 물(`.` or `L`) -> `waterQ.offer(new int[]{i, j})`
• 백조(`L`) 좌표 저장 -> `map[i][j] = '.'` => 백조인 경우도 물로 취급

 

백조 이동 

• `swanQ`: 오늘 백조 이동
• `nextQ`: 내일 녹으면 건널 수 있는 얼음 앞

static boolean moveSwan() {
    while (!swanQ.isEmpty()) {
        int[] cur = swanQ.poll();

		// 두 백조 만남
        if (cur[0] == swan2[0] && cur[1] == swan2[1]) return true; 

        for (int d = 0; d < 4; d++) {
            int nx = cur[0] + dx[d];
            int ny = cur[1] + dy[d];

            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            if (visited[nx][ny]) continue;
            visited[nx][ny] = true;
			
            // 오늘 이동
            if (map[nx][ny] == '.') swanQ.offer(new int[]{nx, ny});  
            // 내일 이동
            else if (map[nx][ny] == 'X') nextSwanQ.offer(new int[]{nx, ny}); 
        }
    }

    swanQ = nextSwanQ; 
    nextSwanQ = new LinkedList<>();
    return false;
}

 

물 녹이기

• `waterQ`: 오늘 물 있는 곳
• `nextWaterQ`: 내일 물 될 곳

static void melt() {
    while (!waterQ.isEmpty()) {
        int[] cur = waterQ.poll();

        for (int d = 0; d < 4; d++) {
            int nx = cur[0] + dx[d];
            int ny = cur[1] + dy[d];

            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            if (map[nx][ny] == 'X') {
            	// 얼음 녹음
                map[nx][ny] = '.';  
                // 내일 물
                nextWaterQ.offer(new int[]{nx, ny}); 
            }
        }
    }

    waterQ = nextWaterQ;         
    nextWaterQ = new LinkedList<>();
}

---

코드

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

// 백조의 호수
public class boj_3197 {
    static int R, C;
    static char[][] map;
    static boolean[][] visited;
    static Queue<int[]> swanQ = new LinkedList<>();
    static Queue<int[]> nextSwanQ = new LinkedList<>();
    static Queue<int[]> waterQ = new LinkedList<>();
    static Queue<int[]> nextWaterQ = new LinkedList<>();
    static int[] swan1, swan2;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static boolean moveSwan() {
        while (!swanQ.isEmpty()) {
            int[] cur = swanQ.poll();

            if (cur[0] == swan2[0] && cur[1] == swan2[1]) return true;

            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d];
                int ny = cur[1] + dy[d];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if (visited[nx][ny]) continue;
                visited[nx][ny] = true;

                if (map[nx][ny] == '.') swanQ.offer(new int[]{nx, ny});
                else if (map[nx][ny] == 'X') nextSwanQ.offer(new int[]{nx, ny});
            }
        }

        swanQ = nextSwanQ;
        nextSwanQ = new LinkedList<>();
        return false;
    }

    static void melt() {
        while (!waterQ.isEmpty()) {
            int[] cur = waterQ.poll();

            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d];
                int ny = cur[1] + dy[d];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if (map[nx][ny] == 'X') {
                    map[nx][ny] = '.';
                    nextWaterQ.offer(new int[]{nx, ny});
                }
            }
        }

        waterQ = nextWaterQ;
        nextWaterQ = new LinkedList<>();
    }

    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 cnt = 0;
        for (int i = 0; i < R; i++) {
            String s = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = s.charAt(j);

                if (map[i][j] != 'X') {
                    waterQ.offer(new int[]{i, j});
                }

                if (map[i][j] == 'L') {
                    if (cnt == 0) swan1 = new int[]{i, j};
                    else swan2 = new int[]{i, j};
                    cnt++;
                    map[i][j] = '.';
                }
            }
        }

        swanQ.offer(swan1);
        visited[swan1[0]][swan1[1]] = true;

        int day = 0;
        while (true) {
            if (moveSwan()) {
                System.out.println(day);
                return;
            }
            melt();
            day++;
        }
    }
}