[BOJ 14503] 로봇 청소기

문제 링크 : https://www.acmicpc.net/problem/14503

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 $N \times M$ 크기의 직사각형으로 나타낼 수 있으며, $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 $(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 $(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 $(N-1, M-1)$이다. 즉, 좌표 $(r, c)$는 북쪽에서 $(r+1)$번째에 있는 줄의 서쪽에서 $(c+1)$번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 $90^\circ$ 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

입력

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽, $1$인 경우 동쪽, $2$인 경우 남쪽, $3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 $N$개의 줄에 각 장소의 상태를 나타내는 $N \times M$개의 값이 한 줄에 $M$개씩 입력된다. $i$번째 줄의 $j$번째 값은 칸 $(i, j)$의 상태를 나타내며, 이 값이 $0$인 경우 $(i, j)$가 청소되지 않은 빈 칸이고, $1$인 경우 $(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

---

풀이

로봇 청소기가 정해진 규칙에 따라 방을 이동하며 청소하는 과정을 구현하는 시뮬레이션 문제다. 문제에서 제시한 작동 순서를 정확하게 코드로 옮기는 것이 핵심이며, 로봇의 위치 $(r, c)$와 바라보는 방향 $d$를 상태값으로 관리해야 한다.

로봇의 동작은 크게 세 단계로 나눌 수 있다.

1. 현재 위치 청소: 현재 칸이 청소되지 않은 상태라면 청소하고 점수를 올린다. 소스 코드에서는 CLEANED (2) 상태를 별도로 정의하여 벽(1)과 빈 칸(0)을 구분하였다.
2. 주변 탐색: 현재 위치의 상하좌우 4칸을 확인한다. 만약 청소되지 않은 빈 칸이 하나라도 있다면, 로봇은 반시계 방향으로 $90^\circ$ 회전하며 전진할 곳을 찾는다.
3. 후진 및 종료: 주변 4칸에 청소할 칸이 없다면, 바라보는 방향을 유지한 채 한 칸 후진한다. 만약 뒤쪽이 벽이라 후진할 수 없다면 작동을 멈춘다.

방향 전환은 $0$(북), $1$(동), $2$(남), $3$(서)로 정의된 숫자를 활용한다. 반시계 방향 회전은 현재 방향에서 $1$을 빼는 연산으로 구현할 수 있으며, 음수가 나오는 것을 방지하기 위해 다음과 같은 나머지 연산을 활용한다.

\[next\_d = (d - 1 + 4) \pmod 4\]

방의 크기는 $N \times M$이며 각각 최대 $50$으로 매우 작다. 로봇이 모든 칸을 최대 한 번씩 청소하고 탐색하므로 전체 시간 복잡도는 $O(NM)$이 되며, 이는 약 $2\,500$번의 연산으로 제한 시간 $2$초 내에 매우 여유롭게 통과 가능하다. 문제의 조건 중 “후진할 수 있다면 1번으로 돌아간다”는 부분은 반복문을 통해 상태를 유지하도록 구현하였다.

소스코드

Github Link : Source Code

참고 알고리즘 :