백준 3196번 백조의 호수(C++)

문제

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

3197번: 백조의 호수

정답 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define X first 
#define Y second 

using namespace std;

/* 
- X: 빙판
- .: 물
- L: 오리
*/
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
char duck='1';
char table[1501][1501];
bool vis[1501][1501];
bool wvis[1501][1501];
int R,C;
queue<pair<int,int>> LQ[2];
queue<pair<int,int>> RQ[2];
queue<pair<int,int>> WQ[2];

bool leftBfs(int day){
	while (!LQ[day%2].empty()){
		auto q = LQ[day%2].front();
		LQ[day%2].pop();
		vis[q.Y][q.X] = true;
		for(int i=0;i<4;i++){
			int ny = q.Y + dy[i];
			int nx = q.X + dx[i];
			if (ny < 0 || nx < 0 || ny >= R || nx >= C)
				continue;
			if (table[ny][nx] == '2')
				return true;
			if (vis[ny][nx] == true)
				continue;
			if (table[ny][nx] == '.'){
				vis[ny][nx] =true;
				table[ny][nx] = '1';
				LQ[day%2].push({nx,ny});
			}
			else if (table[ny][nx] == 'X'){
				vis[ny][nx] = true;
				table[ny][nx] = '1';
				LQ[(day+1)%2].push({nx,ny});
			}
			
		}
	}
	return false;
}

bool rightBfs(int day){
		while (!RQ[day%2].empty()){
		auto q = RQ[day%2].front();
		RQ[day%2].pop();
		vis[q.Y][q.X] = true;
		for(int i=0;i<4;i++){
			int ny = q.Y + dy[i];
			int nx = q.X + dx[i];
			if (ny < 0 || nx < 0 || ny >= R || nx >= C)
				continue;
			if (table[ny][nx] == '1')
				return true;
			if (vis[ny][nx] == true)
				continue;
			if (table[ny][nx] == '.'){
				vis[ny][nx] =true;
				table[ny][nx] = '2';
				RQ[day%2].push({nx,ny});
			}
			else if (table[ny][nx] == 'X'){
				vis[ny][nx] = true;
				table[ny][nx] = '2';
				RQ[(day+1)%2].push({nx,ny});
			}
		}
	}
	return false;
}

void waterBfs(int day){
	if (day == 0){
		for(int i=0;i<R;i++){
			for(int j=0;j<C;j++){
				if (table[i][j] == '.'){
					WQ[0].push({j,i});
					wvis[i][j] = true;
				}
			}
		}
	}
	while (!WQ[day%2].empty()){
		auto q = WQ[day%2].front();
		WQ[day%2].pop();
		wvis[q.Y][q.X] = true;
		for(int i=0;i<4;i++){
			int ny = q.Y + dy[i];
			int nx = q.X + dx[i];
			if (ny < 0 || nx < 0 || ny >= R || nx >= C)
				continue;
			if (wvis[ny][nx] == true)
				continue;
			if (table[ny][nx] == '.'){
				wvis[ny][nx] =true;
				WQ[day%2].push({nx,ny});
			}
			else if (table[ny][nx] == 'X'){
				wvis[ny][nx] = true;
				table[ny][nx] = '.';
				WQ[(day+1)%2].push({nx,ny});
			}
		}
	}
}

int main(){
	cin >>R>>C;
	for(int i=0;i<R;i++){
		for(int j=0;j<C;j++){
			char tmp;
			cin >>tmp;
			if (tmp == 'L'){
				tmp = duck;
				duck++;
				if (LQ[0].empty())
					LQ[0].push({j,i});
				else
					RQ[0].push({j,i});
			}
			table[i][j] = tmp;
		}
	}
	// print_table();
	//BFS좌우 진행
	//진행하다가 벽을 만나면 벽을 현재 다음 큐에 Push 후 해당 위치 vis처리, 해당 맵을 현재 오리로 변경
	int day = 0;
	while (true){
		if (leftBfs(day))
		{
			cout << day<< "\\n";
			return 0;
		}
		if (rightBfs(day)){
			cout << day+1 << "\\n";
			return 0;
		}
		waterBfs(day);
		day++;
	}
}

문제 풀이의 흐름

백조의 호수 문제입니다. 저는 문제를 크게 3가지의 bfs를 따로 돌리는 방법으로 해결했습니다.

문제 예제 입력을 가져와서 풀이해보겠습니다.

..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

문제 예제에서 다음과 같이 그래프가 주어지면 저는 오리를 두개로 구분해서 1번오리 2번오리로 구분하였습니다.

..XXX...X..
.X.XXX...1.
....XXX..X.
X.2..XXX...

두마리의 오리를 먼저 bfs를 해보겠습니다.

22XXX111X11
2X2XXX11111
2222XXX11X1
X2222XXX111

그럼 다음과 같은 모양이 됩니다.

이후 물에 대한 bfs를 진행해야 하는데 그것도 같이 진행해주면 되지만 현재 예제에서는 없기 때문에 그냥 넘어갑니다.

다음으로 저희는 큐에 1이 닿은 벽을 push해주고 또 2를 돌리는 큐에 2가 닿은 벽들을 push해줍니다.

설명을 위해 닿은 벽을 A와 B라고 해보겠습니다.

22BXA111A11
2B2BXA11111
2222BXA11A1
B2222BXA111

다음과 같은 모양이 되고

또다시 1과 2로 바꿔서 bfs를 돌려주는 걸 반복하다가 1과 2가 만나는 경우, 날짜를 출력해주면 정답을 구할 수 있습니다.

주의 할 점

저는 처음에 물을 bfs안 하다가 나중에 추가해서 풀었습니다.

둘이 만나는 날짜가 두번째 오리가 bfs할 때 만나면 +1을 해줘야만 합니다.

반성 및 고찰

플레 문제라고, 쫄 필요 없는 문제고 천천히 조건들 보면서 bfs하면 되는 문제입니다.

큐를 배열로 사용해서 하루를 걸러서 사용하는 방식에 익숙해지면 풀기 쉬운 문제입니다.