[백준]14503번: 로봇 청소기

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

14503번: 로봇 청소기

---

정답률이 높아서 금방 풀 줄 알았는데, 생각보다는 시간이 걸렸었던 문제.

 

문제의 정확한 규칙을 이해하는 게 쉽진 않았다.

그래도 이해하고 나서는 어떻게 어떻게 하라는대로 그대로 구현하니 정답 판정을 받긴 했당

 

---

내가 푼 방법은 이렇다.

0. 청소하는 칸의 개수를 count라고 하고, 청소완료된 칸은 2로 표시하기로 했다.

1. 시작좌표를 큐에 담고 bfs를 시작한다.

2. 현재 칸이 0이라면, 현재 칸 값을 2로 바꾸어주고 count를 증가시켜준다.

3. 반시계방향으로 돌면서, 바로 앞 칸이 0이라면 전진한다.

4. 반시계방향으로 4번 돌았는데도 0인 칸을 발견하지 못하면, 뒤로 한 칸 후진한다.

5. 2~4 과정을 반복한다.

6. 벽에 막혀 후진이 불가능해지면 청소(탐색)를 끝낸다.

---

코드에 대한 약간의 설명

 

1. 현재 방향 정보 표시하기

처음에는 큐에 좌표정보를 넣을때 방향정보까지 같이 넣으려고 했는데,

오히려 번거롭고 헷갈려질 것 같아서

차라리 현재 방향을 나타내는 변수 d를 따로 만들고, 업데이트시켜가며 사용하기로 했다.

d = 0,1,2,3 중 하나

 

2. 반시계방향 회전

현재 방향 d = 0,1,2,3일 때 --> 반시계방향으로 회전하면 방향은 각각 3,0,1,2가 된다.

rotate=[3,0,1,2]로 선언해두면, 현재방향 d가 반시계방향으로 회전한 결과는 rotate[d]가 된다.

 

3. 후진

후진할 때에는 방향 d는 갱신하지 말고 그대로 둬야한다.

위치만 한 칸 뒤로 옮겨가야한다.

 

현재 방향이 0일 때는 아래로 한 칸 가야 한다. (x, y) --> (x+1, y)

현재 방향이 1일 때는 왼쪽으로 한 칸 가야 한다. (x, y) --> (x, y-1)

현재 방향이 2일 때는 위로 한 칸 가야 한다. (x, y) --> (x-1, y)

현재 방향이 3일 때는 오른쪽으로 한 칸 가야 한다. (x, y) --> (x, y+1)

 

따라서 아래와 같은 배열 두개를 미리 만들어두면,

backX, backY = [1,0,-1,0], [0,-1,0,1]

 

현재 좌표 x, y에서 방향이 d일때 후진하는 칸의 좌표는 아래와 같이 나타낼 수 있게 된다.

nextX, nextY = x + backX[d] , y + backY[d]

 

---

정답 코드

from collections import deque
import sys
input = sys.stdin.readline
 
#반시계회전
rotate=[3,0,1,2]
#후진
backX=[1,0,-1,0]
backY=[0,-1,0,1]
#북,동,남,서쪽 방향 이동
dx=[-1,0,1,0]
dy=[0,1,0,-1]

n,m = map(int,input().split())
r,c, d = map(int,input().split())
room=[]
for i in range(n):
  room.append(list(map(int,input().split())))

cnt = 0

q=deque()
q.append((r,c))
while q:
  x, y = q.popleft()
  
  #청소되지 않았으면 청소한다.
  if room[x][y]==0:
    cnt += 1
    room[x][y]=2
    
  #반시계방향으로 4번 돌면서 최초로 청소되지 않은 칸을 찾으면 전진한다.
  for i in range(4):
    d=rotate[d] #현재방향 update시켜주기
    nx,ny = x+dx[d], y+dy[d]
    if 0<=nx<n and 0<=ny<m:
      if room[nx][ny]==0:
        room[nx][ny]=2
        cnt += 1
        q.append((nx,ny))
        break

  #주변 네 칸 중에 청소되지 않은 칸이 없는 경우, 후진한다.
  if len(q)==0:
    nx, ny = x+backX[d], y + backY[d]
    if 0<=nx<n and 0<=ny<m:
      #후진했는데 청소 안 된 칸이면 청소한다.
      if room[nx][ny]==0:
        room[nx][ny]=2
        cnt +=1
        q.append((nx,ny))
      #후진했는데 청소 된 칸이면 그냥 후진한다.
      elif room[nx][ny]==2:
        q.append((nx,ny))
      #후진했는데 벽이면 청소를 멈춘다.
      elif room[nx][ny]==1:
        break
        
#청소한 칸의 개수를 출력한다.
print(cnt)