[BOJ/Gold 4] 백준 23747 와드(C++)

문제 링크

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

23747번: 와드

 

문제

한별이는 출근하던 도중 이세계 대환장 버스에 치였다.

그림 B.1: 이세계 대환장 버스

그림 B.2: 출근하는 한별이

올해 휴가를 전부 써 버려 당장 판교로 돌아가야 하는 한별이는 돌아가기 위한 방법을 어떻게든 찾아보기 위해 이세계를 돌아다녀 보려고 한다.

이세계는 R×C의 격자로 되어 있다. 지금은 밤이어서 한별이는 자신이 위치한 칸 및 그 칸에서 위, 아래, 왼쪽 또는 오른쪽으로 인접한 칸만을 볼 수 있지만, 와드를 설치하면 조금 더 넓은 영역의 시야를 확보할 수 있다. 구체적으로는, 격자의 모든 칸은 각각 어떤 영역 하나에 속해 있는데, 와드를 놓으면 와드가 놓인 칸이 속한 영역에 있는 모든 칸을 볼 수 있게 된다.

한별이의 여행 기록이 주어질 때 한별이가 얼마나 넓은 시야를 확보했을지 계산해 보자.

입력

첫 번째 줄에는 격자의 크기를 나타내는 두 정수 R과 C가 주어진다. (1≤R,C≤1000)

다음 줄부터 R개의 줄에 걸쳐 격자의 정보가 주어진다. 각 줄은 C개의 알파벳 소문자로 이루어져 있으며, 위, 아래, 왼쪽 또는 오른쪽으로 인접해 있는 칸이 같은 문자라는 것은 두 칸이 같은 영역에 속해 있음을 의미한다.

다음 줄에는 한별이가 이세계에 떨어진 위치를 나타내는 두 정수 HR, HC가 주어진다. 이는 한별이가 위에서 HR번째 줄, 왼쪽에서 HC번째 칸에 떨어졌음을 의미한다. (1≤HR≤R, 1≤HC≤C)

마지막 줄에는 한별이의 여행 기록을 나타내는 200000글자 이하의 문자열이 주어진다. 여행 기록의 각 문자는 U, D, L, R, W 중 하나로 이루어져 있으며, U, D, L, R은 각각 위, 아래, 왼쪽, 오른쪽으로 한 칸 이동했다는 뜻이고, W는 지금 있는 칸에 와드를 설치했다는 뜻이다. 한별이가 격자를 벗어나는 경우는 주어지지 않는다.

출력

 R개의 줄에 걸쳐 한별이의 시야를 출력한다. 각 줄은 C개의 문자로 되어 있어야 하며, R번째 줄 C번째 문자가 .이라면 한별이의 시야에 해당 칸이 들어와 있다는 뜻이고 #이라면 그렇지 않다는 뜻이다.

예제 입력 1

4 5
aaabc
dcbbc
dccaa
ddaaa
3 4
WLLLWUURRD

예제 출력 1

##.##
....#
.#...
.....

예제 입력 2

3 3
abc
def
ghi
2 2
LU

예제 출력 2

..#
.##
###

와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다.

지나온 경로를 모두 시야로 확보하지는 않는다.

알고리즘 분류

• 구현
• 그래프 탐색
• 유니온 파인드

풀이

BFS를 이용하여 같은 알파벳을 가진 인접한 영역끼리 유니온 파인드로 묶어준다.

그리고 이동 경로를 확인하면서 와드를 박은 영역은 영역의 Parent만 시야를 밝혀준다면(#를 .로 바꾼다면) 유니온 파인드로 묶인 다른 칸, 즉 같은 영역의 다른 칸의 시야는 Parent를 이용하여 확인할 수 있다.

마지막으로, 이동이 끝난 후 현재 위치와 동서남북은 무조건 시야가 확보되어 있으므로 #에서 .로 바꿔준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int R, C, HR, HC;
string Tour;
char MAP[MAX][MAX];
pair<int, int> Parent[MAX][MAX];
bool visited[MAX][MAX];
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };
char answer[MAX][MAX];
bool Here[MAX][MAX];

void Init() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			Parent[i][j] = make_pair(i, j);
			answer[i][j] = '#';
		}
	}
}

pair<int, int> Find(pair<int, int> A) {
	if (Parent[A.first][A.second] == make_pair(A.first, A.second)) {
		return make_pair(A.first, A.second);
	}
	return Parent[A.first][A.second] = Find(Parent[A.first][A.second]);
}

void Union(pair<int, int> A, pair<int, int> B) {
	pair<int, int> PA = Find(A);
	pair<int, int> PB = Find(B);
	if (PA != PB) {
		Parent[PB.first][PB.second] = PA;
	}
}

void BFS(int Y, int X) {
	queue<pair<int, int> > Q;
	Q.push(make_pair(Y, X));
	visited[Y][X] = true;

	while (!Q.empty()) {
		int CurY = Q.front().first;
		int CurX = Q.front().second;
		Q.pop();

		if (Find(make_pair(CurY, CurX)) != Find(make_pair(Y, X))) {
			Union(make_pair(Y, X), make_pair(CurY, CurX));
		}

		for (int i = 0; i < 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && !visited[nextY][nextX] && (MAP[CurY][CurX] == MAP[nextY][nextX])) {
				visited[nextY][nextX] = true;
				Q.push(make_pair(nextY, nextX));
			}
		}
	};
}

void Input() {
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		string S;
		cin >> S;
		for (int j = 1; j <= C; j++) {
			MAP[i][j] = S[j - 1];
		}
	}
	Init();
	cin >> HR >> HC;
	cin >> Tour;
}

void Settings() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (!visited[i][j]) {
				BFS(i, j);
			}
		}
	}
	for (int i = 0; i < Tour.size(); i++) {
		int CMD = Tour[i];
		if (CMD == 'U') {
			HR--;
		}
		else if (CMD == 'D') {
			HR++;
		}
		else if (CMD == 'L') {
			HC--;
		}
		else if (CMD == 'R') {
			HC++;
		}
		else if (CMD == 'W') {
			pair<int, int> P = Find(make_pair(HR, HC));
			answer[P.first][P.second] = '.';
		}
	}
	Here[HR][HC] = true;
	for (int i = 0; i < 4; i++) {
		Here[HR + moveY[i]][HC + moveX[i]] = true;
	}
}

void Find_Answer() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (Here[i][j]) {
				cout << '.';
			}
			else {
				pair<int, int> P = Find(make_pair(i, j));
				if (answer[i][j] == '#') {
					cout << answer[P.first][P.second];
				}
				else {
					cout << answer[i][j];
				}
			}
		}
		cout << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}