[BOJ] 14503 로봇청소기 (C++)

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

14503번: 로봇 청소기

 

이 문제에서 해석이 헷갈릴 수 있는 부분이 있다.

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

왼쪽에 있는 모든 칸을 확인하라는 의미로 해석할 수 있으며, 그래서 잘못 구현했었음.

 

질문을 확인해봤는데, 비슷한 질문이 있었고, 수정을 했다고 했는데 수정이 되어있지 않았음.

 

왼쪽의 한칸만 확인을 하면 된다.

 

BFS 로 풀이

헷갈렸던 부분은 방향 전환 부분이었는데 

인자로 들어온 방향은 오른쪽으로 회전인 반면,

실제 회전방향은 왼쪽으로 회전한다.

따라서 실제 회전방향을 초기 상단 설정 dy, dx 의 회전으로 고려하기 위해서는 idx 를 3씩 증가 시켜주면 된다.

 

후진의 경우 +2

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct POS {
	int y, x, d;
};

const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int N, m, res;
int map[51][51];
bool visit[51][51];


int solve(POS pos) {

	queue <POS> q;

	q.push(pos);
	
	while(!q.empty()) {

		POS cur = q.front(); q.pop();

		if(map[cur.y][cur.x] == 0) {
			map[cur.y][cur.x] = 2;
			res++;
		}
		
		POS n;
		for(int dir=0; dir<4; dir++) {
			n.d = (cur.d + 3 + (dir*3)) % 4;
			n.y = cur.y + dy[n.d];
			n.x = cur.x + dx[n.d];

			
			if(n.y < 0 || n.y >= N || n.x < 0 || n.x >= m
				|| map[n.y][n.x] != 0) {
				continue;
			}

			q.push(n);
			break;

		}

		if(q.empty()) {
			n.d = cur.d;
			n.y = cur.y + dy[(n.d + 2) % 4];
			n.x = cur.x + dx[(n.d + 2) % 4];

			if(n.y < 0 || n.y >= N || n.x < 0 || n.x >= m || map[n.y][n.x] == 1) {
				return res;
			}

			q.push(n);

		}
	}

	return res;

}





int main() {

	scanf("%d %d", &N, &m);

	POS pos;
	scanf("%d %d %d", &pos.y, &pos.x, &pos.d);

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

	res = solve(pos);


	printf("%d\n", res);
	return 0;
}