백준 3197 - 백조의 호수

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

3197번: 백조의 호수

문제 설명

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

문제풀이

BFS를 진행하면서 백조가 다른 백조를 만날 수 있는지를 체크하고, 못 만났다면 얼음을 녹이고 다시 만날 수 있는지 확인했다. 이 과정에서 첫번째 백조의 위치를 옮기지 않고 시작지점부터 체크를 하려고 하니 시간 초과가 발생했다. 그래서 물이 아닌 얼음이 만나면 그 자리를 기억하고 다음 BFS에서는 기억해놓은 위치에서부터 시작하도록 큐를 하나 더 추가해서 관리해줬다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static class Point{
		int x,y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}
	}
	static int R,C,meet;
	static char[][] map;
	static Queue<Point> 백조 = new ArrayDeque<>();
	static Queue<Point> 얼음 = new ArrayDeque<>();
	static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
	static Point 백조2;
	static boolean[][] visited;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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];
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j]=='L'&&백조.size()==0) {
					백조.add(new Point(i,j));
					얼음.add(new Point(i,j));
				}
				else if(map[i][j]=='L'&&백조.size()==1) {
					백조2 = new Point(i,j);
					얼음.add(new Point(i,j));
				}
				else if(map[i][j]=='.') {
					얼음.add(new Point(i,j));
				}
			}
		}
		ice();
		System.out.println(meet);
	}
	
	static void ice() {
		boolean[][] visited = new boolean[R][C];
		while(!얼음.isEmpty()) {
			int size = 얼음.size();
//			print();
			if(swan()) return;
			for(int depth=0; depth<size; depth++) {
				Point temp = 얼음.poll();
				for(int i=0; i<4; i++) {
					int nx = temp.x+deltas[i][0];
					int ny = temp.y+deltas[i][1];
					if(nx<0 || R <= nx || ny<0 || C <= ny || visited[nx][ny]) continue;
					if(map[nx][ny]=='X') {
						visited[nx][ny] = true;
						map[nx][ny] = '.';
						얼음.add(new Point(nx,ny));
					}
				}
			}
//			System.out.println(meet);
		}
	}
	
	static boolean swan() {
//		boolean[][] visited = new boolean[R][C];
		Queue<Point> 백조_카피 = new ArrayDeque<>(백조);
		백조.clear();
		while(!백조_카피.isEmpty()) {
			Point temp = 백조_카피.poll();
			visited[temp.x][temp.y] = true;
			for(int i=0; i<4; i++) {
				int nx = temp.x+deltas[i][0];
				int ny = temp.y+deltas[i][1];
				if(nx<0 || R <= nx || ny<0 || C <= ny || visited[nx][ny]) continue;
				if(map[nx][ny]=='L') {
					return true;
				}
				else if(map[nx][ny] == '.') {
					visited[nx][ny] = true;
					백조_카피.add(new Point(nx,ny));
				}
				else if(map[nx][ny]=='X') {
					visited[nx][ny] = true;
					백조.add(new Point(nx,ny));
				}
			}
		}
		meet++;
		return false;
	}
}