로봇청소기

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

삼성 기출문제이다.

매우 어려운 문제였다. 문제 이해 자체가 어렵다.

BFS로 해결할 수 있다.

풀이

1. 현재 위치를 청소한다.

2. 현재위치에서 바라보는 방향의 왼쪽 방향을 확인한다.

   ( 이 작업을 4번 진행한다. 그렇다면, 현재위치의 동서남북 모든 방향을 확인 할 수 있다.)

3. 청소를 해야할 구역이고, 아직 방문하지 않았으면 방문한다.

4. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진한다.

5. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

다음 그림에서와 같이 처음 시작은 (7,4) 에서 시작하고, 방향은 북쪽(0)을 바라보고 있다고 하자.

최종 움직임은 다음과 같이 그려질 것이다.

다음 그림의 파란색 지점에서 어떻게 움직이는지 확인해보자. 파란색 지점은 (8,4) 에서 동쪽(1)을 바라보고 있다.

우선 파란색 지점의 방향에서 왼쪽방향(동쪽의 서쪽 방향) 인 북쪽(0)을 확인한다.

이미 방문하였으므로, 이제 북쪽의 왼쪽방향인 서쪽방향을 확인한다.

이미 방문하였으므로, 이제 서쪽의 왼쪽방향인 남쪽방향을 확인한다.

아직 방문하지 않았고, 청소를 해야하는 구역이므로 방문한다. 따라서 다음과 같이 이동을 하게 된다.