[Python] 백준 14503번 - 로봇 청소기 (골드 5)

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

14503번: 로봇 청소기

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 구현
 - 시뮬레이션

 

문제

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

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

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

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

입력

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

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

출력

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

---

이 문제를 풀 때 아무리 해도 예제 2의 57이 나오지 않았다.

 

이해가 안돼서 질문게시판을 살펴보니 나처럼 문제 자체를 이해 못 한 사람들이 꽤 많은 것을 알 수 있었다.

 

애초에 문제 자체도 여러 번의 수정과 오타/지적 과정을 거친 문제로 설명이 디테일하지 않은 문제인 것 같다.

 

https://www.acmicpc.net/board/view/117993

글 읽기 - 로봇 주변에 닦을 수 있는 곳이 있다면, 무조건 90도 회전해 방향을 틉니다!

 

질문 게시판에서 위 글을 보고 문제를 다시 풀어보니 예제와 같은 정답이 나왔다.

 

처음부터 로봇이 왼쪽으로 90도 꺾고 시작한다는 것이다.

 

import sys
input = sys.stdin.readline

from collections import deque

n, m = map(int, input().split())
r, c, d = map(int, input().split())

#주어진 입력 d는 동쪽이 1, 서쪽이 3으로 주어짐
if d == 1:
    d = 3
elif d == 3:
    d = 1

rooms = []
for _ in range(n):
    rooms.append(list(map(int, input().split())))

q = deque()
q.append((r, c))

#북 서 남 동
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
cnt = 0
while q:
    x, y = q.popleft()
    if rooms[x][y] == 0:
        rooms[x][y] = 2
        cnt += 1
    b_clean = False #4방향 청소 여부, 더러운방이 있으면 True 없으면 False

    for i in range(4):
        d = (d+1) % 4
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < n and 0 <= ny < m:
            if rooms[nx][ny] == 0:
                b_clean = True
                break
        
    if b_clean:
        q.append((nx, ny))
    else:
        nx = x - dx[d]
        ny = y - dy[d]
        if 0 <= nx < n and 0 <= ny < m and rooms[nx][ny] == 1:
            print(cnt)
            #for i in range(n):
                #print(rooms[i])
            exit()
        else:
            q.append((nx, ny))

주어진 문제에서는 동쪽과 서쪽이 시계방향, 문제를 풀 때는 반시계방향으로 돌아야 하기 때문에 초기에 숫자를 바꿔서 진행해 주었다.

 

이후는 흔한 bfs문제처럼 큐에 넣고 조건에 맞게 반복이다.