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

#3197 백조의 호수

난이도 : 플레 5

유형 : 그래프 탐색 / BFS

3197번: 백조의 호수

▸ 문제

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

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

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

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

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

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

▸ 입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

▸ 출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

 

문제 풀이  

출발점과 도착점이 만나게 되는 시점을 구하는 문제로 BFS 탐색을 통해 해결할 수 있다. 다만, 맵의 최대 크기가 1500x1500이기 때문에 메모리와 시간복잡도를 단축시켜야 하는 과제가 있다. 일단 효율성을 생각하지 않고 설계하면 두 개의 메서드로 분리가 가능하다.

 

1. 백조 이동 시뮬레이션

출발점(sx, sy)와 도착점(ex, ey)의 정보는 입력 데이터를 받을 때 얻을 수 있다. 백조가 만날 수 있는지는 두 점에 대해 BFS 탐색을 돌리면 O(V+E) 시간복잡도로 탐색이 가능하다. 

• 여기서 문제가 1,500 x 1,500 = 2,250,000의 정점을 가지는 그래프를 극단적으로 탐색을 하게 된다면 효율성을 통과하지 못한다. 

 

2. 얼음 녹이기

가장자리에 있는 얼음들은 물과 반드시 1면은 맞닿아 있다. 그러므로 한 싸이클마다 물과 맞닿아 있는 점을 녹여주면 된다.

• 물을 탐색하는 부분도 단축이 필요하다 무작정 시작점과 끝점부터 재탐색을 할 수 없기 때문이다.

 

효율성을 높여줄 수 있는 방법은 각 메서드에 큐를 활용하여 위치를 새롭게 갱신해주는 것이다.

1. 백조 이동 시뮬레이션 (위치 갱신)

1. 출발점 백조(sx, sy)가 이동하면 얼음과 맞닿아 있는직전으로 위치를 이동시켜준다.
2. 따라서 다음 탐색에서는 (sx, sy)가 아닌 다음에 녹을 얼음이 맞닿아 있는 지점을 큐에 담아준다.

static boolean move() {
	Queue<int[]> q = new LinkedList<>();
	
	while(!sq.isEmpty()) {
		int[] p = sq.poll();
		int px = p[0], py = p[1];
		if(px == ex && py == ey) {
			return true;
		}
		
		for(int i=0; i<4; i++) {
			int nx = px + dx[i];
			int ny = py + dy[i];
			
			if(nx <0 || ny<0 || nx>c-1 || ny>r-1 || check[ny][nx]) continue;
			
			check[ny][nx] = true;
			if(map[ny][nx] == '.') {
				sq.add(new int[] {nx,ny}); 
			}else if(map[ny][nx] == 'X') { // 다음 탐색지역 새로운 큐에 담기
				q.add(new int[] {nx,ny});
			}
		}
	}
	
	sq = q; // 위치 갱신 
	return false;
}

 

2. 얼음 녹이기 (위치 갱신)

1. 물의 위치를 담은 큐는 입력 데이터때 따로 담아준다.
2. 얼음을 녹일 때마다 현재 위치에 담긴 물을 모두 소진하여 인접한 얼음을 녹여주고, 다음 싸이클에 녹을 얼음의 위치를 새롭게 큐에 담아준다.

static void melting() {
	int size = wq.size();
	for(int i=0; i<size; i++) {
		int[] p = wq.poll();
		
		for(int d=0; d<4; d++) {
			int nx = p[0] + dx[d];
			int ny = p[1] + dy[d];
			
			if(nx <0 || ny<0 || nx>c-1 || ny>r-1) continue;
			if(map[ny][nx] == 'X') {
				map[ny][nx] = '.';
				wq.add(new int[] {nx,ny}); // 새로운 물 위치 갱신 
			}
		}
	}
}

 

이와 같이하면 매 번 반복된 지역을 재탐색해도 되지않으므로 효율성테스트에 통과할 수 있다.

설계

1. char[][] map에 입력 데이터를 받는다. 
   1. sx, sy, ex, ey에 대한 정보를 받고 해당 맵 데이터를 '.'로 바꿔준다.
   2. 물의 위치를 큐에 담아준다.
2. (sx, sy)를 시작으로 시뮬레이션을 돌려준다.
   1. 백조 이동하기 move()
      1. BFS 탐색으로 물인 지역만 이동하며 얼음과 맞닿아 있는 지점에서 백조를 멈춘다.
      2. 멈춘 지점을 백조 위치를 담는 큐에 저장한다. (다음 탐색의 (sx,sy)가 된다.)
      3. 만약 (ex, ey)에 도착하면 시뮬레이션을 종료시킨다.
   2. 얼음 녹이기 melting()
      1. 입력 데이터에서 담은 물을 탐색하여 인접해있는 얼음을 녹여준다.
      2. 이전에 탐색한 지역을 재탐색할 필요가 없으므로 방금 녹인 얼음의 위치를 새로운 물 위치를 담은 큐로 갱신해준다.

 

풀이 코드 

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

public class Main {

	static int r,c,ex,ey;
	static char[][] map;
	static boolean[][] check;
	static Queue<int[]> wq,sq;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	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];
		wq = new LinkedList<>();
		sq = new LinkedList<>();
		int sx = -1, sy = -1;
		int idx=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') {
					if(sx==-1 && sy==-1) {
						sx = j;
						sy = i;
					}else {
						ex = j;
						ey = i;
					}
					map[i][j] ='.';
				}
				
				if(map[i][j] == '.') {
					wq.add(new int[] {j,i});
				}
			}
		}
		
		check = new boolean[r][c];
		sq.add(new int[] {sx,sy});
		check[sy][sx] = true;
		
		int time=0;
		while(true) {
			if(move()) break;
			melting();
			time++;
			
		}
		System.out.println(time);
	}
	
	static boolean move() {
		Queue<int[]> q = new LinkedList<>();
		
		while(!sq.isEmpty()) {
			int[] p = sq.poll();
			int px = p[0], py = p[1];
			if(px == ex && py == ey) {
				return true;
			}
			
			for(int i=0; i<4; i++) {
				int nx = px + dx[i];
				int ny = py + dy[i];
				
				if(nx <0 || ny<0 || nx>c-1 || ny>r-1 || check[ny][nx]) continue;
				
				check[ny][nx] = true;
				if(map[ny][nx] == '.') {
					sq.add(new int[] {nx,ny}); 
				}else if(map[ny][nx] == 'X') { // 다음 탐색지역 
					q.add(new int[] {nx,ny});
				}
			}
		}
		
		sq = q;
		return false;
	}
	
	static void melting() {
		int size = wq.size();
		for(int i=0; i<size; i++) {
			int[] p = wq.poll();
			
			for(int d=0; d<4; d++) {
				int nx = p[0] + dx[d];
				int ny = p[1] + dy[d];
				
				if(nx <0 || ny<0 || nx>c-1 || ny>r-1) continue;
				if(map[ny][nx] == 'X') {
					map[ny][nx] = '.';
					wq.add(new int[] {nx,ny});
				}
			}
		}
	}
}