[백준 14503] 로봇 청소기 (C++) - G5

문제

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

14503번: 로봇 청소기

 

개요

처음 풀어본 시뮬레이션 문제이다.

일단 직접 그림을 그려보지 않고 머릿속으로만 생각하다보니까 문제 설명을 이해하는 데 굉장히 오래 걸렸다.

그리고, 시뮬레이션 문제라는 사실에 미리 겁을 먹은 것도 있다.

시뮬레이션 문제는 뭔가 특별한 방식을 사용하는 줄 알고 DFS, BFS를 사용하면 안 될 것 같다는 착각에 빠졌다.

그래서 굉장히 이상한 함수 구현에 힘을 들였고, 결국 이 문제 또한 구글링의 힘을 빌렸다...

 

문제 설명에 대한 이해는 직접 태블릿으로 그림을 그려보니까 쉽게 이해할 수 있었다.

다음은 문제에 주어진 예제 2와 그에 대한 풀이 그림이다.

 

문제 풀이

이 문제는 BFS로 풀 수도 있고, DFS로 풀 수도 있다.

사실 문제 풀이에 장황하게 글로 쓸 내용은 많지 않고, 코드를 따라가다 보면 쉽게 이해할 수 있을 것이다.

 

BFS 코드에서 중요한 부분을 2군데만 꼽자면 다음과 같다.

 

첫번째 부분은 다음 코드이다.

int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 }; // 순서 : 북(0), 동(1), 남(2), 서(3)

for (int i = 0; i < 4; i++) {
	int nd = (cd + (3 - i)) % 4; // 시계 반대 방향 회전 (0 -> 3 -> 2 -> 1)
	int ny = cy + dy[nd];
	int nx = cx + dx[nd];

위 코드는 사실 기존의 BFS 코드에 등장하는 코드와 크게 다르지 않다.

다른 점은 이 문제에는 방향에 대한 개념이 존재한다는 것이다.

방향은 4가지 방향이 존재하고, 시계 반대 방향으로 회전하면서 현재 바라보는 방향을 바꾼다.

문제에 따르면, 0은 북쪽, 1은 동쪽, 2는 남쪽, 3은 서쪽을 의미한다.

따라서, 시계 반대 방향으로 회전함에 따라, 0 → 3 → 2 → 1 → 0 이런 식으로 회전한다.

 

위의 내용을 바탕으로 nd를 구하는 식을 작성한 것이다.

일단 방향이 4개 단위로 반복되며 회전하기 때문에 nd를 구하는 식의 마지막에는 4로 나눠주는 % 4 부분이 있을 것이라는 사실은 예상할 수 있다.

따라서, nd = (cd + x) % 4 이런 형태가 될 것이다.

이제 우리는 x에 해당하는 식만 구하면 되는 것이다.

예를 들어, 현재 cd = 0이라고 해보자. 즉, 현재 바라보는 방향이 북쪽인 것이다.

i = 0이면, 시계 반대 방향으로 90도 한 번 회전한 것이기 때문에 nd = 3(서쪽)이 나와야 하므로, x = 3이다.

i = 1이면, 시계 반대 방향으로 90도 한 번 더 회전한 것이기 때문에 nd = 2(남쪽)가 나와야 하므로, x = 2이다.

i = 2이면, 시계 반대 방향으로 90도 한 번 더 회전한 것이기 때문에 nd = 1(동쪽)이 나와야 하므로, x = 1이다.

i = 3이면, 시계 반대 방향으로 90도 한 번 더 회전한 것이기 때문에 nd = 0(북쪽)이 나와야 하므로, x = 0이다.

즉, 위의 4가지 경우로부터 x = 3 - i 임을 알 수 있고, 결론적으로 nd = (cd + (3 - i)) % 4 라는 식을 얻을 수 있다.

 

두번째 부분은 다음 코드이다.

// 네 방향 모두 청소되어 있는 경우
if (!flag) { 

	// 현재 바라보고 있는 방향 유지한 채로 한 칸 후진
	int by = cy - dy[cd];
	int bx = cx - dx[cd]; 

	if (by < 0 || bx < 0 || by >= n || bx >= m) continue;

	// 후진한 위치가 벽이 아니면
	if (arr[by][bx] != 1) {
		q.push({ {by, bx}, cd });
	}
}

위 코드는 현재 위치에서 네 방향 모두 청소되어 있는 경우에 대한 코드이다.

현재 바라보고 있는 방향(cd)를 유지한 채로 한 칸 후진한 위치 (by, bx)를 구한 후에, 그 위치가 벽이 아니라면, 즉 arr[by][bx]가 1이 아니라면 현재 바라보는 방향 cd와 함께 queue에 push해준다.

 

코드

BFS 풀이

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

#define INF (~0U >> 2) // 약 10억 7천만 (1073741823)

using namespace std;

int n, m, ans;
int arr[50][50];
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 }; // 순서 : 북(0), 동(1), 남(2), 서(3)

void bfs(int y, int x, int d) {
	
	queue <pair<pair<int, int>, int>> q;
	q.push({ {y, x}, d });
	
	while (!q.empty()) {
		int cy = q.front().first.first;
		int cx = q.front().first.second;
		int cd = q.front().second; // 현재 바라보고 있는 방향
		
		if (arr[cy][cx] == 0) {
			arr[cy][cx] = 2; // 청소 완료
			ans++;
		}
		q.pop();

		bool flag = false; // true : 네 방향 중에 청소되지 않은 빈 칸 있음
		for (int i = 0; i < 4; i++) {
			int nd = (cd + (3 - i)) % 4; // 시계 반대 방향 회전 (0 -> 3 -> 2 -> 1)
			int ny = cy + dy[nd];
			int nx = cx + dx[nd];

			if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;

			if (arr[ny][nx] == 0) {
				q.push({ {ny, nx}, nd });
				flag = true;
				break;
			}
		}

		// 네 방향 모두 청소되어 있는 경우
		if (!flag) { 

			// 현재 바라보고 있는 방향 유지한 채로 한 칸 후진
			int by = cy - dy[cd];
			int bx = cx - dx[cd]; 

			if (by < 0 || bx < 0 || by >= n || bx >= m) continue;

			// 후진한 위치가 벽이 아니면
			if (arr[by][bx] != 1) {
				q.push({ {by, bx}, cd });
			}
		}
	}
}

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

	cin >> n >> m;
	int y, x, d; cin >> y >> x >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	bfs(y, x, d);
	cout << ans;
	return 0;
}

 

DFS 풀이

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

#define INF (~0U >> 2) // 약 10억 7천만 (1073741823)

using namespace std;

int n, m, ans;
int arr[50][50];

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

void dfs(int cy, int cx, int cd) {
	
	if (arr[cy][cx] == 0) {
		arr[cy][cx] = 2;
		ans++;
	}

	for (int i = 0; i < 4; i++) {
		int nd = (cd + (3 - i)) % 4;
		int ny = cy + dy[nd];
		int nx = cx + dx[nd];

		if (nx < 0 || ny < 0 || ny >= n || nx >= m) {
			continue;
		}

		if (arr[ny][nx] == 0) {
			dfs(ny, nx, nd);
		}
	}

	int by = cy - dy[cd];
	int bx = cx - dx[cd];

	if (arr[by][bx] == 1) {
		cout << ans;
		exit(0);
	}
	dfs(by, bx, cd); // 현재 바라보는 방향을 유지한 채 후진
}


int main(void) {
	cin >> n >> m;

	int y, x, d;
	cin >> y >> x >> d;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	dfs(y, x, d);

	return 0;
}

 

깨달은 점

시뮬레이션 문제라고 해서 뭔가 크게 다른 유형이 아니고, 오히려 DFS, BFS를 더 잘 다룰 줄 알아야 한다는 것을 깨닫게 되었다.