BOJ 14503 로봇 청소기

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

시뮬레이션 문제는 왜 이렇게 말을 복잡하게 하는 걸까..

이번 문제도 이해는 어렵고 구현은 더 어려웠다. 결국 다른 풀이를 참고해서 풀었다.

구현 문제는 풀고 보면 참 쉬운 것 같다..

 

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

 

이번 문제에서 헷갈리는 것은 2.2를 어떻게 구현할 것인가가 문제인 것 같다.

d를 BFS 형식으로 배열에서 왓다갓다 하면서 청소해주면 되는데 결국 어떻게 처리하냐 문제였다.

 

#include <cstdio>

int n, m, r, c, d, ans;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int ar[51][51];

int dirback(int d) {
	if (d == 0) return 2;
	else if (d == 1) return 3;
	else if (d == 2) return 0;
	else return 1;
}

int main() {
	scanf("%d%d", &n, &m);
	scanf("%d%d%d", &r, &c, &d);

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			scanf("%d", &ar[i][j]);

	while (1) {
		//case 1
		if (ar[r][c] == 0) {
			ar[r][c] = 2; 
			ans++; 
		}
		
		bool chk = false;
		for (int i = 0; i < 4; ++i) {
			d = (d == 0) ? 3 : d - 1; //case 2.a
			int nx = r + dx[d];
			int ny = c + dy[d];

			if (ar[nx][ny] == 0) { //case 2.b
				r = nx;
				c = ny;
				chk = true;
				break;
			}
		}
		if (chk) continue;

		//case 2.c 
		int p = dirback(d);
		r += dx[p];
		c += dy[p];

		//case 2.d
		if (ar[r][c] == 1) break;
	}

	printf("%d\n", ans);

	return 0;
}

 

구간별로 처리해보면 

 

case 1 일 때는 0을 청소해야 하니 2로 처리해두고 카운트를 하나 올려준다.

 

이후 4번을 왓다갓다 하면서 중간에 청소할 곳이 나온다면 멈추고 처음으로 돌아간다.

이때, case 2.b 에서 청소하지 말고 case 1로 돌아와서 청소해줘야 한다.

 

4번의 반복문이 모두 끝난다면 4방향 모두에 청소할 곳이 없다는 뜻이니

후진할 방향을 함수로 작성해줬다.

처음에는 int p 가 아니라

d = dirback(d); 로 해줬는데 문제 설명을 잘 읽어보니 방향은 그대로 후진을 하는 거였다..

 

후진할 방향에 벽이 있다면 종료해주면 끝난다.