[백준]14503번 로봇 청소기 (Python/파이썬)

1. 문제 설명

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

로봇 청소기가 있는 방은 𝑁×𝑀 크기의 직사각형으로 나타낼 수 있으며, 1×1 크기의 정사각형 칸으로 나누어져 있다.

각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다.

방의 각 칸은 좌표 (𝑟,𝑐)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0) 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (𝑁−1,𝑀−1)이다. 즉, 좌표 (𝑟,𝑐)는 북쪽에서 (𝑟+1)번째에 있는 줄의 서쪽에서 (𝑐+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

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

로봇 청소기는 위와 같은 matrix에서 움직이는 노드입니다.

 

📌 로봇 청소기의 이동 조건:

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

---

2. 입/출력 설명

1) 입력

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

 

셋째 줄부터 𝑁개의 줄에 각 장소의 상태를 나타내는 𝑁×𝑀개의 값이 한 줄에 𝑀개씩 입력된다. 𝑖번째 줄의 𝑗번째 값은 칸 (𝑖,𝑗)의 상태를 나타내며, 이 값이 0인 경우 (𝑖,𝑗)가 청소되지 않은 빈 칸이고, 1인 경우 (𝑖,𝑗)에 벽이 있는 것이다.

방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다.

로봇 청소기가 있는 칸은 항상 빈 칸이다.

 

2) 출력

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

 

3) 예제

# Example 01
# Input
3 3
1 1 0
1 1 1
1 0 1
1 1 1

# Output
1

 

# Example 02
# Input
11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

# Output
57

---

3. 구현 코드

1) 구현 시 주의사항

로봇 청소기의 이동조건이 구현에서 가장 중요한 부분입니다.

 

📌 로봇 청소기의 이동 조건:

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

여기서 주목해야 할 점은, 3번 조건입니다.

저는 처음에 로봇 청소기가 주변의 청소가 안 된 칸에 90도 회전을 1번만 했을 때, 전진이 불가능하면 멈추는 것으로 이해를 했는데, 청소되지 않은 칸으로 갈 때까지 반시계 방향 회전이 가능합니다.

 

💡 조건 3의 경우, 반시계 방향 회전과 전진

방향에 따른 (x,y) 좌표 이동 값

# 북, 동, 남, 서 방향으로 전진했을 때의 dx, dy
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 4번의 회전
for _ in range(4):
	# 0 -> 3 -> 2 -> 1 -> 0
	d = (d+3) % 4
    
    # 방향의 앞으로 전진
    nx = x + dx[d]
    ny = y + dy[d]

 

이렇게 반시계 방향으로 회전을 4번 해서, 청소를 하지 않은 칸이 있는지를 확인해주어야 합니다.

저는 한 번만 회전해서 이상한 값이 나왔었어요..ㅎㅎ

 

🥕 조건 2의 경우, 후진

if not cleaned:
	# dx를 더하는 게 아니고 빼줌
	nx = x - dx[oD] #oD : 회전 전의 original direction
    ny = y - dy[oD]
    
    # 벽이 아니라면, 큐에 넣음
    if graph[nx][ny] != 1:
    	q.append([nx, ny, oD])

 

dx, dy는 북(0), 동(1), 남(2), 서(3) 순서대로 전진 했을 때의 변화 값입니다.

주변에 청소를 안 한 칸이 없는 경우, 후진을 할 때에는 +dx가 아니라 -dx를 해줘야 합니다.

 

2) 전체 코드

같은 level의 주변 노드들부터 탐색하고, 점차 범위를 확대해 나가는 알고리즘이므로 BFS를 사용해 구현했습니다.

from collections import deque

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

def bfs():
    q = deque()
    q.append([rX, rY, rD])
    cnt = 1
    graph[rX][rY] = -1

    while q:
        cleaned = False
        x, y, d = q.popleft()
        oD = d

        for _ in range(4):
            d = (d+3) % 4
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
                q.append([nx, ny, d])
                graph[nx][ny] = -1
                cnt += 1
                cleaned = True
                break

        if not cleaned:
            nx = x - dx[oD]
            ny = y - dy[oD]
            if graph[nx][ny] != 1:
                q.append([nx, ny, oD])

    print(cnt)

## Main##
N,M = map(int, input().split())
rX,rY, rD = map(int, input().split())
graph = []

for n in range(N):
    graph.append([int(x) for x in input().split()])

bfs()

---

참고 사이트

문제는 백준 사이트에서 확인할 수 있습니다.  문제 바로가기 >>

반시계 방향으로 회전을 몇 번 할 수 있는지, 구현을 어떻게 해야할 지를 몰라서 헤맸는데, 냐항님의 코드를 참고했습니다.

[백준] 14503 - 로봇 청소기 (Python)