백준 3197번 : 백조의 호수 [Java]

문제

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

3197번: 백조의 호수

 

코드

package baekjoon;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_3197 {

	static boolean[][] visited;
	static int[][] map;
	static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
	static Point[] swans;
	static int R, C, waterQueueSize, dayCount = 0;
	static Queue<Point> waterQueue = new ArrayDeque<>(), bfsQueue = new ArrayDeque<>();
	static boolean flag = false;
	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 int[R][C];
		swans = new Point[2];
		visited = new boolean[R][C];
		int swanIdx = 0;
		for(int i = 0; i < R; i++) {
			String str = br.readLine();
			for(int j = 0; j < C; j++) {
				if(str.charAt(j) == '.') { //갈 수 있는 곳
					map[i][j] = 0;
					waterQueue.add(new Point(i, j));
				}
				else if(str.charAt(j) == 'L') { //백조
					map[i][j] = 0;
					swans[swanIdx++] = new Point(i, j);
					waterQueue.add(new Point(i, j));
				}
				else if(str.charAt(j) == 'X') { //얼음
					map[i][j] = 1;
				}
			}
		}
		
		while(!flag) {
			bfs(swans[0].x, swans[0].y);
			
			waterQueueSize = waterQueue.size();
			waterQueueUpdate();
			
			if(flag == true) break;
			
			dayCount++;
		}
		
		System.out.println(dayCount);
		
	}
	
	static void bfs(int x, int y) {
		Queue<Point> nextQueue = new ArrayDeque<>();
		bfsQueue.add(swans[0]);
		visited[x][y] = true;
		while(!bfsQueue.isEmpty()) {
			Point now = bfsQueue.poll();
			if(now.x == swans[1].x && now.y == swans[1].y) { //백조가 만남
				flag = true;
				return;
			}
			for(int direction = 0; direction < 4; direction++) {
				int nx = now.x + dx[direction];
				int ny = now.y + dy[direction];
				if(!checkBound(nx, ny) || visited[nx][ny]) continue;
				visited[nx][ny] = true;
				if(map[nx][ny] == 1) { //얼음은 다음날 백조가 탐색할 지역
					nextQueue.add(new Point(nx, ny));
				}
				else {
					bfsQueue.add(new Point(nx, ny));
				}
				
			}
		}
		bfsQueue = nextQueue;
	}

	static void waterQueueUpdate() {
		for(int i = 0; i < waterQueueSize; i++) {
			Point nowWater = waterQueue.poll();
			for(int direction = 0; direction < 4; direction++) {
				int nx = nowWater.x + dx[direction];
				int ny = nowWater.y + dy[direction];
				if(checkBound(nx, ny) && map[nx][ny] != 0) {
					map[nx][ny] = 0;
					waterQueue.add(new Point(nx, ny));
				}
			}
		}
	}
	
	static boolean checkBound(int x, int y) {
		if(x < 0 || x >= R || y < 0 || y >= C) return false;
		return true;
	}
}

 

일단 이건 도저히 못 풀겠어서 다른 사람들의 풀이를 많이 참고했다.

 

내가 처음 접근 했던 풀이 방법

하루가 지날때마다 얼음을 녹이면서 백조가 만날 수 있는가 없는가를 확인 해주었다.

얼음을 녹일 때는 2차원 배열을 돌면서 각각의 시작점에 대해서 bfs를 수행하면서 얼음을 만나면 얼음을 녹이고 return.

백조가 만날 수 있는가 없는가도 bfs로 탐색하면서 확인 해주었다.

그랬더니 시간 초과가 나버렸다. 입력값 범위를 확인을 안 했다.

시간을 줄이려면 수많은 bfs를 줄이는 방법으로 가는게 맞다는 생각이 들었다.

 

인터넷에 검색해서 나오는 풀이들도 그렇고 알고리즘 스터디 사람들이 풀이한 방법을 봐도 그렇고 보통은 큐를 3개를 사용하는 경우가 많았다.(FloodFill + UnionFind로 푸신 분 제외...)

 

1. 입력 받는 과정에서 백조위치 = 물 같은 취급 하여 map에는 0으로 얼음이라면 1로 저장

 

2. 1번 과정에서 함께 <<물위치를 저장하는 큐>>에 좌표 저장 + 백조 위치는 따로 저장

 

3. 첫번째 백조의 위치를 시작으로 bfs를 수행

 

4. <<bfs를 진행하는 큐>>와 <<다음번 bfs를 수행할 때 사용할 큐>> 두가지를 사용한다. 

<<bfs를 진행하는 큐 >>는 그냥 일반적으로 진행하는 bfs처럼 진행을 해준다.

• bfs를 수행하는 중에 두번째 백조와 now가 일치하게 되면 flag를 true로 바꿔주고 return한다.
• 사방탐색을 진행하며 얼음을 만나면 <<다음번 bfs를 수행할 때 사용할 큐>>에 해당 좌표 값을 넣는다.
• 얼음이 아닌 지역이라면 <<bfs를 진행하는 큐>>에 좌표를 넣는다.
• bfs탐색을 한번 마치게 되면 <<bfs를 진행하는 큐>>를 <<다음번 bfs를 수행할 때 사용할 큐>>로 바꿔준다.

5.<<물 위치를 저장하는 큐>>의 사이즈를 따로 저장한다.

 

6. 5에서 저장한 큐의 사이즈만큼만 poll하며 해당 물 주변의 사방 한칸씩을 녹여주고 녹여준 좌표 값을 <<물 위치를 저장하는 큐>>에 넣어준다.

 

7.flag가 false라면 dayCount를 증가시키고 다시 4번으로 돌아간다.

 

이렇게 진행되면 처음에 내가 접근했던 방법보다 bfs를 호출하는 횟수가 훨씬 줄어들게 된다.

이런 문제가 코테로 나온다면 정말 멘붕에 빠질거 같다...

bfs를 할때 큐를 여러개 사용하는 방법에 대한 기억을 하고 있는게 좋을거 같다.