[P5] 백준 3197번 백조의 호수 C++ 플러드 필, BFS, 유니온 파인드

리뷰

 

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

드디어 풀었다.. X를 미리 방문처리 안해주다 보니 메모리가 터지고, 미리 방문처리 해주면 LXL 같은 케이스에서 답이 0이 나와서 고심하다가 적절한 해법이 떠올라 적용했더니 바로 AC를 받았다.

 

 

전역 변수

• r, c : 맵의 세로 변의 길이 r, 맵의 가로 변의 길이 c
• idx : 분리 집합의 인덱스를 지정하기 위한 변수
• ans : 정답을 저장하고 출력하기 위한 변수
• dx, dy : 4방향 탐색을 위한 방향 배열
• lst : 맵 정보를 받기 위한 문자열 배열
• v : 맵 상의 분리집합을 표시하기 위한 정수형 2차 배열
• Pos : 시뮬레이션을 할때 좌표 및 그룹 정보를 식별하기 위한 구조체
• nodes : 그룹의 소속을 관리하기 위한 정수형 벡터
• ice : 제거될 예정인 얼음 정보가 담긴 Pos타입의 큐
• swan : 초기 단계에서 백조의 플러드 필을 사용하기 위한 Pos타입의 배열

 

함수

1. input

void input()

 

값을 입력 받고 변수 및 자료 구조를 초기화 하기 위한 함수

1. r, c값을 입력 받고 r번의 반복문을 통해 문자열을 입력 받아준다.
2. c번의 반복문을 통해 입력 받은 문자열을 탐색하고 백조의 위치를 찾아준다.
3. 각각의 백조의 그룹을 1, 2번으로 설정하고 swan배열에 위치 및 그룹 정보를 저장해 준다.

 

2. Find

int Find(int a)

 

현재 번호의 그룹이 속해있는 그룹을 찾기 위한 함수

 

3. Union

void Union(int a, int b)

 

b그룹을 a그룹에 속하도록 합치는 함수

1. Find함수를 통해 a, b그룹이 속해있는 그룹 A, B를 구해준다.
2. 만약 A, B가 동일하다면 이미 같은 그룹에 속해있는 것 이므로 리턴 처리해준다.
3. 만약 A, B가 다르다면 B가 속한 그룹을 A가 속한 그룹으로 변경해 준다.

 

4. bfs

void bfs(const Pos& pos)

 

초기 단계에서의 물을 그룹화 해주기 위한 함수

1. x, y좌표 및 속한 그룹 정보를 Pos타입의 구조체의 매개변수로 받아준다.
2. Pos타입의 큐 q를 초기화 하고 q에 매개변수로 받은 pos를 push해준다.
3. 큐가 빌때까지 탐색을 진행한다, 4방향으로 탐색하며 인접한 물을 같은 그룹으로 방문처리 해준다.
4. 만약 X를 만났을 경우 Pos타입의 큐 ice에 추가해 준다.

 

5. init

void init()

 

얼음이 녹기 전 상태의 초기 상태를 체크하기 위한 함수

1. swan에 저장된 두 백조의 Pos정보를 bfs함수에 매개변수로 전달하여 백조에서의 플러드필을 진행한다.
2. 이후 r * c크기의 맵을 탐색하며 물이면서 아직 그룹에 속해있지 않은 경우 그룹을 생성하고 bfs를 진행한다.

 

6. melt

void melt()

 

얼음을 녹이는 시뮬레이션을 진행하는 함수

1. 해당 함수가 실행되었다면 한 턴이 진행하는 것이므로 ans를 증가시켜 준다.
2. 큐에서 얼음 정볼를 꺼내 얼음을 물로 변경해 주고 4방향 탐색을 시작한다.
3. 인접한 칸에 그룹이 다른 칸이 있다면 Union처리를 진행해 준다.
4. 만약 인접한 칸이 X라면 ice에 추가해 주고 아니라면 큐에 추가해 준 뒤 방문 처리를 해준다.

 

문제풀이

1. input 함수를 통해 입력을 받아 변수와 자료 구조를 초기화 해준다.
2. init 함수를 통해 얼음이 녹기 전 맵의 정보를 탐색하여 물을 그룹화 해준다.
3. 백조1, 2의 그룹 정보가 동일해 질 때까지 melt함수를 실행해 준다.
4. ans에 저장된 값을 출력해 준다.

 

참고 사항

X를 만났을 경우 방문 처리는 진행하되 그룹화는 진행하지 않아야 한다.

만약 방문 처리를 하지 않는다면 X좌표가 큐에 중복으로 추가되어 큐가 터져 메모리 초과가 출력된다.

그렇다고 유니온 처리를 해주면 LXL와 같은 경우는 정답이 0으로 출력이 된다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int r, c, idx, ans;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
string lst[1500];
int v[1500][1500];

struct Pos {
	int x, y, g;
};

vector<int> nodes(1, 0);
queue<Pos> ice;
Pos swan[3];

void input() {
	cin >> r >> c;
	for (int i = 0; i < r; ++i) {
		cin >> lst[i];
		for (int j = 0; j < c; ++j) {
			if (lst[i][j] == 'L') {
				idx++;
				swan[idx] = { i, j, idx };
				nodes.push_back(idx);
				v[i][j] = idx;
			}
		}
	}
}

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	//if (a < b) swap(a, b);
	int A = Find(a);
	int B = Find(b);
	if (A == B) return;
	nodes[B] = A;
}

void bfs(const Pos& pos) {
	queue<Pos> q;
	q.push(pos);

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, cg = pos.g;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < r && 0 <= ny && ny < c && Find(v[nx][ny]) != Find(cg)) {
				if (v[nx][ny] && lst[nx][ny] != 'X') Union(cg, v[nx][ny]);
				if (!v[nx][ny]) {
					if (lst[nx][ny] == 'X') ice.push({ nx, ny, cg });
					else q.push({ nx, ny, cg });
					v[nx][ny] = cg;
				}
			}
		}
	}
}

void init() {
	bfs(swan[1]);
	bfs(swan[2]);	

	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j) {
			if (lst[i][j] == '.' && !v[i][j]) {
				idx++;
				nodes.push_back(idx);
				v[i][j] = idx;
				bfs({ i, j, idx });
			}
		}
	}
}

void melt() {
	ans++;
	queue<Pos> q;
	swap(q, ice);

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, cg = pos.g;
		lst[cx][cy] = '.';

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < r && 0 <= ny && ny < c && Find(v[nx][ny]) != Find(cg)) {
				if (v[nx][ny] && lst[nx][ny] != 'X') Union(cg, v[nx][ny]);
				if (!v[nx][ny]) {
					if (lst[nx][ny] == 'X') ice.push({ nx, ny, cg });
					else q.push({ nx, ny, cg });
					v[nx][ny] = cg;
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	init();
	while (Find(1) != Find(2)) melt();
	cout << ans;
}