[백준/파이썬][Gold V] 로봇 청소기 - 14503

[Gold V] 로봇 청소기 - 14503

문제 링크

성능 요약

메모리: 109240 KB, 시간: 116 ms

분류

구현, 시뮬레이션

제출 일자

2023년 11월 13일 12:50:00

문제 설명

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

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

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

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

입력

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

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

출력

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

풀이

def solve(ci, cj, dr) :
    cnt = 0     # 청소한 공간 수
    while 1:    # 청소기가 더이상 움직이지 못할 때 종료
        # 현재 위치 청소
        arr[ci][cj] = 2
        cnt += 1

        # 왼쪽 방향으로 순서대로 탐색해서 미청소 영역이 있는 경우 이동 / 방향 설정, 없으면 후진
        flag = 1
        while flag :
            # 왼쪽부터 네 방향 중 미청소 영역 있는 경우
            for nd in ((dr + 3) % 4, (dr + 2) % 4, (dr + 1) % 4, dr) :
                ni, nj = ci + di[nd], cj + dj[nd]
                if arr[ni][nj] == 0 :   # 미청소 영역
                    ci, cj, dr = ni, nj, nd
                    flag = 0
                    break

            else :    # 네 방향 모두 미 청소 영역 없음 => 후진
                bi, bj = ci - di[dr], cj - dj[dr]   # 후진할 위치
                if arr[bi][bj] == 1 :    # 벽 => 종료
                    return cnt
                else :
                    ci, cj = bi, bj     
    
    # 혹시나 하는 경우
    return -1

N, M = map(int, input().split())
r, c, d = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(N)]

# 0: 북, 1: 동, 2: 남, 3: 서
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

print(solve(r, c, d))

           +-------------------+
           |   시작 (초기화)   |
           +-------------------+
                     |
                     v
        +-------------------------+
        | 현재 위치 청소 여부 확인 |
        +-------------------------+
                     |
           +---------+---------+
           |                   |
           v                   v
   +----------------+   +---------------------+
   | 청소되지 않음  |   | 청소됨 (현재 위치)  |
   +----------------+   +---------------------+
           |                   |
           v                   v
   +----------------+   +---------------------+
   | 현재 위치 청소 |   | 주변 빈 칸 확인    |
   +----------------+   +---------------------+
           |                   |
           v                   v
   +----------------+   +---------------------+
   | 청소 카운트 증가 |   | 주변 4칸 유무 확인  |
   +----------------+   +---------------------+
           |                   |
           v                   |
   +----------------+          |
   | 주변 빈 칸 발견? |   +-------------------+
   +----------------+   |   후진 가능?      |
           |           +-------------------+
           |           |         |         |
           |           |         v         |
           |           |   +---------------+
           |           |   | 후진 및 위치   |
           |           |   +---------------+
           |           |         |
           |           |         v
           |           |   +-----------------+
           |           |   | 작동 종료 (벽)  |
           |           |   +-----------------+
           |           |
           |           v
           |   +---------------------+
           |   | 빈 칸으로 이동 (전진) |
           |   +---------------------+
           |                 |
           +-----------------+
                     |
                     v
           +-------------------+
           |  다시 시작 (1번)  |
           +-------------------+

위와 같은 구조로 돌아간다.