[백준/Python] 14503 로봇청소기

 

전형적인 구현 문제이다.

문제에서 주어진 풀이 과정을 따라가며 풀면 된다.

방의 구조가 주어지고, 특정 위치에서 동서남북을 비교해가며 푸는 문제이므로 BFS를 활용해 구현했다.

반시계 방향으로 돌리는 걸 어떻게 구현해야할지 고민을 많이 했는데,

북(0)->서(3) / 서(3)->남(2) / 남(2)->동(1) / 동(1)->북(0) 임을 고려해

(d+3) % 4라는 식을 만들어냈다.

 

N, M = map(int, input().split())
i, j, d = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]

# 1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
visited[i][j] = 1
cnt = 1

dx = [-1, 0, 1, 0]  # 북(0)->서(3), 서(3)->남(2), 남(2)->동(1), 동(1)->북(0)
dy = [0, 1, 0, -1]  # 북->서, 서->남, 남->동, 동->북


while True:
    flag = 0
    # 3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
    for _ in range(4):
        nx = i + dx[(d+3)%4]
        ny = j + dy[(d+3)%4]
        d = (d+3) % 4  # 3-1. 반시계 방향으로 90도 회전한다.

        # 3-2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
        if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                cnt += 1
                i, j = nx, ny
                flag = 1
                break
    # 2. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 없는 경우,
    if flag == 0:
        # 2-1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
        if room[i - dx[d]][j - dy[d]] != 1:
            i, j = i-dx[d], j-dy[d]
        # 2-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
        else:
            print(cnt)
            break

풀이과정

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

문제에서 주어진 풀이과정을 그대로 활용했다.