백준 BOJ 3197 - 백조의 호수

상당히 까다로웠던 문제

좀 푸는데 오래걸렸다

 

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

3197번: 백조의 호수

 

구하고자 하는 걸리는 날을 T라고 할때,

매일매일 vis배열을 초기화하면서 호수를 탐색하면

시간초과나 메모리초과를 받게 된다.

 

첫째날에 대부분을 미리 탐색해 놓고,

두번째 날부터는 얼음과 물의 경계선에 해당하는 부분에서만 탐색을 진행해주면

연산량이 극적으로 감소하면서 시간초과 / 메모리초과 둘다 잡히는듯.

 

큐 두개를 활용해서 호수가 녹는 부분에 대한 관리를 진행해 줬고

녹게 될 부분, 즉 빙판과 물이 맞닿아있는 부분의 빙판을 '#' 으로 갱신하면서

임시 처리를 진행해줬다.

 

두 백조가 만났는지 만나지 못했는지의 확인은

유니온파인드 자료구조를 활용해서 만들어줬다.

일차원적인 값에 대한 유니온파인드가 아니기 때문에

2차원 좌표쌍을 저장할수 있게끔 pair<int,int> 로 저장해줬다.

 

함수의 호출을 줄이면 메모리 초과를 받을 확률을 줄일 수 있다.

나는 유니온 파인드에 필요한 find와 joint(union연산) 함수 두개 빼고는

전부 메인함수에 넣었다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

pair<int,int> parent[1515][1515];
pair<int,int> swan0;
pair<int,int> swan1;

int N,M;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

queue<pair<int,int>> q1;
queue<pair<int,int>> q2;

string arr[1515];

bool vis[1515][1515] = {0};

pair<int,int> find(pair<int,int> pos){
	if(parent[pos.x][pos.y] == pos) return pos;
	return parent[pos.x][pos.y] = find(parent[pos.x][pos.y]);
}

void joint(pair<int,int> a, pair<int,int> b){
	a = find(a);
	b = find(b);
	parent[a.x][a.y] = b;
	return;
}

int main(){
	cin >> N >> M;
	bool flag = true;
	for(int i=0; i<N; i++){
		cin >> arr[i];
		for(int j=0; j<M; j++){
			parent[i][j] = {i,j};
			
			if(arr[i][j] == '.'){
				q2.push({i,j});
			}
			
			if(arr[i][j] == 'L'){
				arr[i][j] = '.';
				q2.push({i,j});
				if(flag) { swan0 = {i,j}; flag = false; }
				else     { swan1 = {i,j}; }
			}
		}
	}
	
	int ans = 0;
	while(true){
		while(!q2.empty()){ q1.push(q2.front()); q2.pop(); }
		
		while(!q1.empty()){
			int x = q1.front().x;
			int y = q1.front().y;
			q1.pop();

			vis[x][y] = true;
		
			for(int i=0; i<4; i++){
				int nx = x+dx[i];
				int ny = y+dy[i];

				if((0<=nx && nx<N) && (0<=ny && ny<M)){
					
					if(arr[nx][ny] == 'X') arr[nx][ny] = '#';
			
					if((arr[nx][ny] == '.') && !vis[nx][ny]) q1.push({nx,ny});
					if((arr[nx][ny] == '.') && vis[nx][ny])  joint({x,y},{nx,ny});
				}
			}
		}
		
		if(find(swan0) == find(swan1)) break;
		
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				if(arr[i][j] == '#'){
					q2.push({i,j});
					arr[i][j] = '.';
				}
			}
		}
		ans++;
	}
	cout << ans;
	return 0;
}