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

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

접근

N,M의 크기가 50 이하이고, 로봇청소기가 한번 청소한 곳은 청소하지 않고, 탈출 조건도 비교적 간단하여 그냥 구현하면 될 것 같다고 판단하였다.
또한 지도의 가장자리는 항상 벽이라 배열의 범위를 넘어서는 것을 고려하지 않아도 된다.

풀이

로봇청소기가 작동하는 방식 그대로 코드로 옮기면 된다.

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

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
clean = True

while 1:
    if clean:
        board[r][c] = 2  # 청소 완료
        ans += 1

    clean = False
    for i in range(1, 5):  # 네 방향 탐색
        ny, nx = r + dy[(d - i) % 4], c + dx[(d - i) % 4]
        if board[ny][nx] == 0:
            clean = True
            r, c, d = ny, nx, (d - i) % 4
            break  # 네 방향 중 청소할 곳 있음
    if clean:
        continue

    # 네 방향 중 청소할 곳 없음
    ny, nx = r + dy[(d - 2) % 4], c + dx[(d - 2) % 4]
    if board[ny][nx] != 1:  # 후진, 벽 아님
        r, c = ny, nx
    else:  # 벽이라 후진 못함
        break

1. 우선 처음에 청소를 한다. 로봇 청소기가 처음 놓인 곳은 항상 빈공간이기 때문에 처음에 clean변수는 무조건 True. 청소 후엔 clean을 False로 바꿔준다.
2. 이제 탐색의 시간이다
   2-1, 2-2. 현재 방향에서 반시계방향(왼쪽)으로 탐색한다. dy,dx가 차례대로 북 동 남 서 방향으로 만들어주었기 때문에 탐색은 그와 반대방향으로 돌아가게끔 하였다(ny, nx = r + dy[(d - i) % 4], c + dx[(d - i) % 4]). 만약 탐색중에 청소하지 않은 빈공간을 발견하면 clean을 True로 바꿔주고, 위치와 방향을 모두 그 방향에 맞게 설정한다.
   2-3. 만약 네 방향을 모두 탐색했는데 청소할 곳이 없으면, 뒤로 후진한다. 이때 후진할 곳이 벽이 아니여야 한다. 이때 위치는 바뀌지만 방향은 그대로다.
   2-4. 종료 조건이다. 네 방향 모두 청소할 곳이 없고, 후진도 할 수 없다면 청소가 종료되어 반복문을 탈출한다.

정답코드

n, m = map(int, input().split())
r, c, d = map(int, input().split())  # 0 1 2 3 / 북 동 남 서
board = [list(map(int, input().split())) for _ in range(n)]


dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

clean = True
ans = 0

while 1:
    if clean:
        board[r][c] = 2  # 청소 완료
        ans += 1

    clean = False
    for i in range(1, 5):  # 네 방향 탐색
        ny, nx = r + dy[(d - i) % 4], c + dx[(d - i) % 4]
        if board[ny][nx] == 0:
            clean = True
            r, c, d = ny, nx, (d - i) % 4
            break  # 네 방향 중 청소할 곳 있음
    if clean:
        continue

    # 네 방향 중 청소할 곳 없음
    ny, nx = r + dy[(d - 2) % 4], c + dx[(d - 2) % 4]
    if board[ny][nx] != 1:  # 후진, 벽 아님
        r, c = ny, nx
    else:  # 벽이라 후진 못함
        break
print(ans)