[G5] 백준 23747번 와드 C++ 플러드 필, 너비 우선 탐색

리뷰

 

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

맵이 두개인 이세계 대환장 문제, 메타버스 느낌이 들어 재밌었다.

 

 

전역 변수

• n, m : 맵의 세로/가로 길이를 저장할 변수
• sx, sy : 초기 위치에서 이세계의 이동 좌표를 저장할 변수
• lst : 이세계 맵 정보를 저장할 배열
• orders : 한별이의 여행 기록을 저장할 변수
• ans : 현실세계 맵 정보를 저장할 배열
• v : 방문 정보를 저장할 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 플러드 필을 할 때 위치 정보 x, y를 정의할 구조체

 

함수

1. floodfill

void floodfill()

 

플러드 필을 통해 같은 그룹의 시야를 밝히기 위한 함수

1. Pos타입의 큐 q를 초기화 하고, 현재 위치 sx, sy를 push해준다.
2. ans의 sx, sy에 '.'를, v의 sx, sy에 방문 처리를 진행해 준다.
3. q가 빌 때 까지 while 루프를 순회하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
4. 현재 위치에서 4방향 탐색을 진행하고, 맵의 범위 안이면서 같은 그룹에 속하고, 방문하지 않았다면 이동을 진행한다.
5. 이동 후엔 방문처리 및, ans에 '.'로 기록해 주고, q에 이동한 위치를 삽입해 준다.

 

문제풀이

1. n, m값을 입력 받고, n * m크기의 맵을 입력 받으면서 ans는 모두 '#'으로 초기화 해준다.
2. sx, sy, orders를 입력 받고, 0-based-indexing을 위해 sx, sy를 각각 1만큼 줄여준다.
3. 변수 idx를 -1로 초기화 하고, idx를 전위증가한 값이 orders.size()보다 작을 때 까지 while루프를 돌려준다.
4. 매 루프마다 변수 op에 orders의 idx값을 받아 여행 기록에 맞게 로직을 진행해 준다.
5. op가 'U'라면 sx를 1만큼 빼내어 준다.
6. op가 'D'라면 sx를 1만큼 더해 준다.
7. op가 'L'라면 sy를 1만큼 빼내어 준다.
8. op가 'R'라면 sy를 1만큼 더해 준다.
9. op가 'W'라면 floodfill 함수를 호출해 준다.
10. while루프가 종료되었다면 현재 sx, sy위치와 4방향의 ans값을 모두 '.'로 변경해 준다.
11. ans에 저장된 값을 n * m크기만큼 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 여행 기록에서 한별이가 격자를 벗어나는 경우는 주어지지 않는다.
• 와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다.
• 지나온 경로를 모두 시야로 확보하지는 않는다.

 

정답 코드

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

int n, m, sx, sy;
string lst[1000], orders;
char ans[1000][1000];
bool v[1000][1000];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y;
};

void floodfill() {
	queue<Pos> q;
	q.push({ sx, sy });
	ans[sx][sy] = '.';
	v[sx][sy] = true;

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

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] == lst[sx][sy] && !v[nx][ny]) {
				v[nx][ny] = true;
				ans[nx][ny] = '.';
				q.push({ nx, ny });
			}
		}
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		for (int j = 0; j < m; ++j) {
			ans[i][j] = '#';
		}
	}

	cin >> sx >> sy >> orders;
	--sx, --sy;
	int idx = -1;
	while (++idx < orders.size()) {
		const char& op = orders[idx];
		if (op == 'U') sx -= 1;
		else if (op == 'D') sx += 1;
		else if (op == 'L') sy -= 1;
		else if (op == 'R') sy += 1;
		else floodfill();
	}
	ans[sx][sy] = '.';
	for (int i = 0; i < 4; ++i) {
		int nx = sx + dx[i], ny = sy + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m) ans[nx][ny] = '.';
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << ans[i][j];
		}
		cout << "\n";
	}
}