14503번: 로봇 청소기

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

14503번: 로봇 청소기

 

 어제 오늘 이틀동안 붙잡고 있었던 문제다. 유사한 문제들이 많기 때문에 깊이 우선 탐색(DFS)를 이용하여 구현하였는데 답이 1~2개씩 차이가 나는 것 때문에 오늘까지 붙잡게 되었다. 이유는 문제를 잘못 이해한 것이었는데, 문제에서 후진을 못할 경우 멈추는 조건이 모든 방향을 탐색하여도 후진할 경로가 없을 때인줄 잘못 이해한 것이 문제였다.

 

[문제 접근]

 일단 DFS인지 BFS인지 부터 분류해보자. 로봇이 한 군데(A)를 탐색하고 그곳(A)을 기점으로 다시 탐색 한다면 DFS, 다시 제자리(B)에서 다른 방향(C,D,E)을 모두 탐색한 후 다시 처음 부분(A)을 탐색한다면 BFS로 구현해야한다. 

 

 이 문제에서는 로봇이 왼쪽 방향(A)을 탐색하고 그 위치(A)를 기점으로 다시 탐색하므로 DFS로 구현해야 한다. 벽으로 막혀 갈 수 없다면 벽을 건너뛰고 가는 것이 안되므로 main문에서 for문을 돌릴 필요가 없다. (로봇이 벽을 뛰어 넘거나 해서 각각의 영역 수를 세야한다면 for문에서 0,0 부터 N-1,M-1까지 돌려주어야한다). 따라서 main에서 dfs를 한번 돌린다.

 

 DFS의 알고리즘은 기본적인 틀과 같다. 여기서 다른 점은 네 방향 모두 벽이거나 청소가 되어있을 때 후진하는 부분을 구현해주어야 한다는것. 이는 제자리로 돌아가는 것이 아니라 제자리에서 후진을 해야하기 때문에 x,y에 back_x, back_y를 넣어준 후 stack에 push한다.

 

[코드]

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

int N, M; // 맵 크기
int map[51][51];
bool check[51][51];

int dr[4] = { 0, -1, 0, 1 };
int du[4] = { -1, 0, 1, 0 };
int back_x[4] = { 1, 0, -1, 0 };
int back_y[4] = { 0, -1, 0, 1 };

int dfs(int x, int y, int d) {
	int area = 1;
	check[x][y] = true; // 현재 위치 청소
	stack<pair<int, int>> stk;

	stk.push({ x,y });
	
	while (!stk.empty()) {
		x = stk.top().first; y = stk.top().second;
		stk.pop();

		int cnt = 0; // 벽 갯수 카운트
		int tcnt = 0;
		int org_d = d;
		for (int i = 0; i < 4; i++) { // 네 방향(단순히 네번 도는것)
			int nx = x + dr[d];
			int ny = y + du[d];

			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue; // 맵 바깥으로 나가면
			else if (map[nx][ny] == 1) { // 벽이면
				cnt++; // 벽 갯수 카운트
			}
			else if (check[nx][ny] == true) {
				cnt++;
			}

			if (cnt == 4) { // 네 방향 모두 벽이거나 청소 되어있을 때
				d = org_d;
				if (map[x + back_x[d]][y + back_y[d]] == 1) { // 지금 방향에서 후진도 벽이면
					break;
				}
				else { // 후진 가능하면
					d = org_d;
					nx = x + back_x[d]; // 후진
					ny = y + back_y[d]; // 후진
					stk.push({ nx,ny });
					break; // 네 방향 다시 탐색 및 벽 갯수 초기회
				}
			}
			

			d--; // 방향 왼쪽으로 틀기
			if (d < 0) d = 3; // 북쪽에서 틀면 서쪽으로(0->3)

			if (map[nx][ny] != 1 && check[nx][ny] == false) { // 청소 안하고 벽도 아니면
				area++; // 청소 영역 추가
				map[nx][ny] = area;
				check[nx][ny] = true; // 청소 체크
				stk.push({ nx ,ny }); // 그 위치로 이동
				break;
			}
		}
	}
	return area;

}

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

	cin >> N >> M;

	int r, c, d; // 로봇 위치, 방향
	cin >> r >> c >> d;


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	cout << dfs(r, c, d);
}