[BOJ 3197] 백조의 호수 (Java)

BOJ 3197 백조의 호수

문제풀이

너무너무너무 어렵다... 보통 이런 유형의 문제는 지시하는 바를 순서대로 반복 수행하면 되는 것이였으나 이 문제는 최악의 경우에 맵이 무려 1500 x 1500 이다. 따라서 매번 새롭게 BFS를 수행한다거나 방문체크를 수행시 마다 리셋하는 것은 불가능하다.

이 문제의 핵심은 다음과 같다.

• 다음 큐와 현재 큐 사이즈만큼만 BFS를 수행를 통해 매번 처음부터 탐색을 수행하는 것이 아니라 이전에 탐색을 중지한 지점에서 이어 진행하는 것이다.
• 백조의 탐색을 위한 탐색 큐, 그리고 다음 탐색 지점을 저장하였다가 탐색 큐와 순환시킬 다음 큐, 얼음에 인접한 물을 담고 있는 워터 큐

구현 순서는 다음과 같다.

1. 데이터를 입력받는다.

   • 백조의 위치를 따로 저장한다.
   • 모든 물(백조의 위치 포함)을 워터 큐에 저장한다.

2. 탐색 큐에 첫 번째 백조를 넣고 방문체크한다.

3. 탐색 큐로 BFS 탐색을 실시한다.

   • 두 번째 백조를 찾았으면 종료한다.
   • 모든 다음 지역을 방문체크하며 얼음을 만났을 시에는 다음 큐에 넣는다.
   • 다음 큐에 들어간 지역들은 다음 날 얼음이 녹아 다음 탐색의 시작점이 된다.

4. 탐색이 종료된 후 다음 큐를 탐색 큐로 바꾼다.

   • 탐색 큐와 다음 큐의 순환을 통해 탐색을 이어서 할 수 있도록 한다.

5. 워터 큐에 있는 물과 인접한 얼음을 녹이고 그 지점을 다시 워터 큐에 넣는다.

   • 시작전 사이즈를 저장하고 그 사이즈만큼만 BFS를 실시하여 오늘 녹아야할 얼음만 녹도록 한다.

6. 날짜를 1 증가시키고 3.으로 돌아간다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Node {
		int r, c;
		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	static Queue<Node> q;
	static Queue<Node> waterQ;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static char[][] map;
	static boolean[][] visited;
	static Node[] swan;
	static int R, C;
	
	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());
		
		waterQ = new LinkedList<>();
		q = new LinkedList<>();
		swan = new Node[2];
		map = new char[R][C];
		visited = new boolean[R][C];
		
		// 데이터 입력
		int swanIdx = 0;
		for(int r = 0 ; r < R ; ++r) {
			char[] line = br.readLine().toCharArray();
			for(int c = 0 ; c < C ; ++c) {
				map[r][c] = line[c];
				if(map[r][c] == 'L') {
					swan[swanIdx++] = new Node(r, c);
				}
				if(map[r][c] != 'X') {
					waterQ.offer(new Node(r, c));
				}
			}
		}
		
		// 출발점이 되는 백조 
		q.offer(swan[0]);
		visited[swan[0].r][swan[0].c] = true;
		
		int day = 0;
		boolean meet = false;
		
		while(true) {
			Queue<Node> nextQ = new LinkedList<>();
			while(!q.isEmpty()) {
				Node now = q.poll();
				
				// 백조를 만날시 종료 
				if(now.r == swan[1].r && now.c == swan[1].c) {
					meet = true;
					break;
				}
				
				for(int d = 0 ; d < 4 ; ++d) {
					int nr = now.r + dir[d][0];
					int nc = now.c + dir[d][1];
					
					if(nr >= R || nr < 0 || nc >= C || nc < 0 || visited[nr][nc]) continue;
					
					visited[nr][nc] = true;
					
					// 물에 인접한 얼음으로 다음 날 백조가 탐색할 지역 
					if(map[nr][nc] == 'X') {
						nextQ.offer(new Node(nr, nc));
						continue;
					}
					// 현재 탐색 가능 지역
					q.offer(new Node(nr, nc));
				}
			}
			
			// 백조가 만났으면 종료 
			if(meet) break;
			// q를 다음날 탐색할 지역이 담긴 nextQ로 바꾼다. 
			q = nextQ;
			
			// 얼음을 녹인다.
			int size = waterQ.size();
			
			for(int i = 0 ; i < size ; ++i) {
				Node now = waterQ.poll();
				
				for(int d = 0 ; d < 4 ; ++d) {
					int nr = now.r + dir[d][0];
					int nc = now.c + dir[d][1];
					
					if(nr >= R || nr < 0 || nc >= C || nc < 0) continue;
					
					// 물에 인접한 얼음을 발견하면 녹이고 다시 큐에 넣는다. 
					if(map[nr][nc] == 'X') {
						map[nr][nc] = '.';
						waterQ.offer(new Node(nr, nc));
					}
				}
			}
			day++;
		}
		
		System.out.println(day);
	}
}