[백준] 3197번 백조의 호수 JAVA

문제

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

3197번: 백조의 호수

 

---

풀이 방법

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

2636번: 치즈

치즈 문제와 유사해서 똑같은 풀이 방법으로 접근할 수 있다.

 

1. 물(백조의 위치도 물임) 주변의 얼음을 녹인다.

2. 한 백조의 위치로부터 BFS를 돌려 다른 백조로 도착할 수 있는지 확인한다.

반복

 

R 과 C의 범위가 크기 때문에 위 방식만으로는 시간 초과가 발생한다.

 

 

 

 

개선이 필요한 부분

1. 녹이는 과정의 개선
2. 백조 만날 수 있는지 확인 과정의 개선

 

---

1. 녹이는 과정의 개선

물(백조의 위치)에서 BFS로 탐색하며 주변의 얼음을 녹인다. 
빨간색 은 BFS의 탐색 범위

 

파란색 부분은 이미 탐색을 했었기 때문에 굳이 BFS를 할 필요가 없다.
Queue에 넣는 동작을 조절하여 필요한 부분만을 탐색하게 하여 시간을 줄일 수 있다.

 

 

 

 

 

 

 

기존에는 Queue를 구성하기 위해 R * C 만큼 돌면서 물인 곳을 Queue에 담았지만,
개선 된 코드는 현재 BFS를 돌면서 다음 BFS에 사용할 Queue를 미리 만든다.

BFS를 진행하면서 얼음을 만난 경우 다음 BFS에 사용할 Queue인 nextq에 넣어준다.
nextq를 이용해 다음 BFS를 돌릴 경우 필요한 부분만을 탐색할 수 있게된다.

 

 

예시

최초에는 nextq가 구성되어 있지 않기 때문에 기존 방식처럼 R * C를 돌며 탐색한다.

BFS 탐색을 하며 얼음이었던 곳을 nextq에 넣어둔다.

 

 

 

 

 

불필요한 방문을 하지 않을 수 있게 된다.

---

 

2. 백조 만날 수 있는지 확인 과정의 개선

백조가 만날 수 있는지 확인하기 위해 BFS 탐색이 필요한 범위

 

 

 

얼음을 녹인 뒤,
백조가 만날 수 있는지 확인하기 위해 BFS 탐색이 필요한 범위

 

-> 시간이 오래걸린다.

 

참고 : 위에서 설명한 개선된 얼음을 녹이는 방식을 적용할 수도 있지만,
여기서는 유니온 파인드 설명을 위해 유니온 파인드를 사용

 

 

물을 집합으로 생각하고, 인접하면 union하는 방식으로 집합을 구성한 뒤,
find 연산으로 같은 집합에 속했는지 확인

 

 

좌표를 주면 해당 좌표 주변의 물과 merge를 수행하는 코드

// 주변의 물과 merge 수행
static void unionForNearWater(int x,int y) {
    for(int i=0;i<4;i++) {
        int gox = x + dx[i];
        int goy = y + dy[i];
        if(!isIn(gox,goy) || map[goy][gox] != '.')continue;
        merge(new Pos(y,x), new Pos(goy,gox));
    }
}

최초에는 R * C를 돌며 물인 칸에서 unionForNearWater()를 호출해준다.

 

 

물을 녹이면서 unionForNearWater()을 호출한다.

 

find연산을 통해 같은 집합에 속해있음을 확인할 수 있다.

---

코드 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Pos {
		int y, x;
		public Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
		static boolean isEqual(Pos a,Pos b) {
			return a.x == b.x && a.y == b.y;
		}
	}
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };
	static int R, C;
	static char[][] map;
	static boolean[][] visited;
	
	// 두 거위의 위치
	static Pos[] L;
	// disjoint set
	static Pos[][] u;
	

	public static void main(String[] args) throws Exception {
		init();
		// 물을 집합으로 표현한다.
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] == '.') {
					unionForNearWater(j,i);
				}
			}
		}
		// 최초 1번은 R * C 만큼 순회하며 BFS를 돌린다.
		// 이후에는 nextq를 이용해서 이 큐에 들어있는 값으로만 BFS 돌린다
		// 한번 visited한 곳은 갈 필요가 없기 때문
		
		Queue<Pos> q = new ArrayDeque<>();
		visited = new boolean[R][C];
		for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				if(map[i][j] == '.') {
					q.add(new Pos(i,j));
					visited[i][j] = true;
				}
			}
		}
		
		int time = 1;
		
		while(true) {
			
			// 얼음을 녹인다.
			q = BFS(q);
			//두 거위의 물이 같은 집합에 속했는지 확인한다.
			if(Pos.isEqual(find(L[0]), find(L[1]))) {
				break;
			}
			time++;
		}
		System.out.println(time);
	}
	
	static Queue<Pos> BFS(Queue<Pos> q) {
		Queue<Pos>nextq = new ArrayDeque<>();
		
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			
			for(int i=0;i<4;i++) {
				int gox = cur.x + dx[i];
				int goy = cur.y + dy[i];
				if(!isIn(gox, goy) || visited[goy][gox])continue;
				
				// 얼음을 녹이고 주변과 union 한다.
				if(map[goy][gox] == 'X') {
					map[goy][gox] = '.';
					visited[goy][gox] = true;
					nextq.add(new Pos(goy,gox));
					unionForNearWater(gox, goy);
				}
				else if(map[goy][gox] == '.') {
					visited[goy][gox] = true;
					q.add(new Pos(goy, gox));
				}
			}
		}
		
		return nextq;
	}

	static void init() throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		u = new Pos[R][C];
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				u[i][j] = new Pos(-1, -1);
			}
		}
		L = new Pos[2];
		int cnt = 0;
		for (int i = 0; i < R; i++) {
			String tmp = in.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = tmp.charAt(j);

				// 백조의 위치를 저장, 물로 바꾼다.
				if (map[i][j] == 'L') {
					L[cnt++] = new Pos(i, j);
					map[i][j] = '.';
				}
			}
		}
	}
	
	// 주변의 물과 merge 수행
	static void unionForNearWater(int x,int y) {
		for(int i=0;i<4;i++) {
			int gox = x + dx[i];
			int goy = y + dy[i];
			if(!isIn(gox,goy) || map[goy][gox] != '.')continue;
			merge(new Pos(y,x), new Pos(goy,gox));
		}
	}

	static Pos find(Pos a) {
		if (u[a.y][a.x].x == -1 && u[a.y][a.x].y == -1) {
			return a;
		}
		return u[a.y][a.x] = find(u[a.y][a.x]);
	}

	static void merge(Pos a, Pos b) {
		a = find(a);
		b = find(b);
		if (a.x == b.x && a.y == b.y)return;
		u[b.y][b.x].x = a.x;
		u[b.y][b.x].y = a.y;
	}

	static boolean isIn(int x, int y) {
		if (x < 0 || x >= C)return false;
		if (y < 0 || y >= R)return false;
		return true;
	}

}