[백준] #14503 로봇 청소기 - 파이썬

문제

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

로봇 청소기가 있는 방은 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)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

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

예제 입력 1 복사

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 1 복사

1

---

복기

1. 처음에는 상하좌우 4칸을 파악하고, 거기서 움직이고 하는 로직이랑 BFS로 풀었다. 하지만 '최단거리' 를 고려하는 것이 아닌 청소한 칸의 수를 카운팅하는 문제였다.

2. 방향 전환을 구현할때 (d+1)%4로 했었는데, 이거는 처음 로직으로 움직이는 시계방향이어서 문제 내용을 제대로 반영 못했었다.

3. 어렵지 않은 문제였는데, 못 푼거는 아직 많이 부족함을 의미하는거 같다. 

---

솔루션

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

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

# 북 동 남 서
dx = [0,1,0,-1]
dy = [1,0,-1,0]

def turn_left(d):
    return (d+3)%4

cnt = 0

while True:
    # 1. 현재 위치 청소
    if visited[r][c] == 0:
        visited[r][c] = 1
        cnt += 1
    
    cleaned = False
    for _ in range(4):
        d = turn_left(d)
        nx, ny = r+dx[d], c+dy[d]
        if 0<=nx<N and 0<=ny<M and arr[nx][ny] == 0 and visited[nx][ny] == 0:
            r, c = nx, ny # 이동
            cleaned = True
            break

    if not cleaned:
        # 후진 시도
        back_d = (d+2)%4
        br, bc = r+dx[back_d], c+dy[back_d]

        if 0<=br<N and 0<=bc<M and arr[br][bc] == 0:
            r,c = br, bc # 후진
        else:
            break

print(cnt)