[Python - implementation] 14503 로봇 청소기

📌 문제

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

 

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

 

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

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

📌 입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

 

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

 

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

 

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

📌 출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

문제의 조건이 좀 난해해서 이해하는 게 가장 오래 걸렸던 문제였다. 여기서 조건을 내 나름대로 다시 해석해보자면 다음과 같다.

 

1. 현재 위치를 청소한다

2. 현재 위치에서 현재 방향을 기준으로 차례대로 왼쪽으로 90˚회전하며 탐색한다.

  ● 2-1. 왼쪽 방향을 청소할 수 있다면, 그 방향으로 회전한 다음 한 칸 전진하고 1번으로 돌아간다.

  ● 2-2. 왼쪽 방향에 청소할 공간이 없다면, 왼쪽으로 회전한 다음 2번으로 돌아가 다시 탐색한다.

  ● 2-3. 청소가 불가능해서 다시 원래의 방향으로 돌아왔을 때(청소가 이미 되어있는 곳도 있고 벽인 곳도 있어서)

    ▶ 2-3-1. 원래의 방향을 유지한 채로 후진할 수 있다면 후진하고 2번으로 돌아간다.

    ▶ 2-3-2. 원래 방향의 반대편 방향에 벽이 있어 후진이 불가능하다면 작동을 멈춘다.

 

조건이 조금 이해하기가 어려웠다.

 

그래프 탐색에서 BFS가 익숙하여 BFS로 풀었는데, 그냥 while 반복문으로 풀어도 가능할 것 같다.

 

일단 준비할 것은, 주어진 입력을 모두 받는 것은 당연하며 방문 테이블(청소 테이블)을 만드는 것이다. 내가 청소한 곳을 벽과 똑같이 1로 갱신해주면, 향후에 후진이 불가능하므로 따로 청소 테이블을 만들었다. 혹은, -1과 같이 방문했다고 별도로 지도에 작성해도 될 것이다.

 

그 다음, 회전을 어떻게 구현할지를 고민했다. 이때 사용한 것이 나누기 연산자였다. 문제에서 반시계 방향으로 90도씩 회전하게 되는데, 이를 direction 리스트에 접목시키고, 인덱스를 적절히 섞어서 간편하게 회전할 수 있도록 했다.

 

예를 들면 아래와 같다.

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

for i in range(1, 6):
	nd = (d + i) % 4

이렇게 하면, 내가 어떤 방향이든지 왼쪽으로 차례차례 탐색이 가능하다.

 

그렇게 한 후에, 어떻게 구현하면 좋은지 문제의 조건을 곱씹으면서 코드를 작성하면 된다.

👨‍🏫 문제 풀이

📄 전체 코드

from collections import deque
import sys
input = sys.stdin.readline

'''
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
  1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
  2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
  3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
  4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
'''


def bfs(r, c, d):
    # 청소 구역 테이블
    visited = [[False] * m for _ in range(n)]
    q = deque()
    q.append((r, c, d))
    visited[r][c] = True
    cnt = 1

    while q:
        x, y, d = q.popleft()
        for i in range(1, 5):  # 4까지 도달했을 때, 비로소 2-3, 2-4 조건으로 넘어감
            nd = (d + i) % 4  # 방향 계산
            nx = x + dx[nd]
            ny = y + dy[nd]
            if not (0 <= nx < n and 0 <= ny < m):
                continue
            if graph[nx][ny] != 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                cnt += 1
                q.append((nx, ny, nd))
                break
        else:  # 4방향 모두 불가능
            if graph[x - dx[d]][y - dy[d]] != 1:
                q.append((x - dx[d], y - dy[d], d))

    return cnt


# n: 세로, m: 가로
n, m = map(int, input().split())

# r: x좌표, c: y좌표, d: 방향
r, c, d = map(int, input().split())

if d == 1:
    d = 3
elif d == 3:
    d = 1

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

# 지도
graph = [list(map(int, input().split())) for _ in range(n)]

# 청소 시작
print(bfs(r, c, d))

📄 준비

from collections import deque
import sys
input = sys.stdin.readline

'''
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
  1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
  2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
  3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
  4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
'''

...

# n: 세로, m: 가로
n, m = map(int, input().split())

# r: x좌표, c: y좌표, d: 방향
r, c, d = map(int, input().split())

if d == 1:
    d = 3
elif d == 3:
    d = 1

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

# 지도
graph = [list(map(int, input().split())) for _ in range(n)]

일단 문제에서 d를 입력할 때, (0, 1, 2, 3)이 문제에서 회전하는 방향과 역방향이므로 d가 1이면 3으로, d가 3이면 1로 변환해주었다.

📄 풀이

...

def bfs(r, c, d):
    # 청소 구역 테이블
    visited = [[False] * m for _ in range(n)]
    q = deque()
    q.append((r, c, d))
    visited[r][c] = True
    cnt = 1

    while q:
        x, y, d = q.popleft()
        for i in range(1, 5):  # 4까지 도달했을 때, 비로소 2-3, 2-4 조건으로 넘어감
            nd = (d + i) % 4  # 방향 계산
            nx = x + dx[nd]
            ny = y + dy[nd]
            if not (0 <= nx < n and 0 <= ny < m):
                continue
            if graph[nx][ny] != 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                cnt += 1
                q.append((nx, ny, nd))
                break
        else:  # 4방향 모두 불가능
            if graph[x - dx[d]][y - dy[d]] != 1:
                q.append((x - dx[d], y - dy[d], d))

    return cnt

...


# 청소 시작
print(bfs(r, c, d))

문제의 2-1, 2-2 조건은 아래의 조건과 같다.

nd = (d + i) % 4  # 방향 계산
nx = x + dx[nd]
ny = y + dy[nd]
if not (0 <= nx < n and 0 <= ny < m):
    continue
if graph[nx][ny] != 1 and not visited[nx][ny]:
    visited[nx][ny] = True
    cnt += 1
    q.append((nx, ny, nd))
    break

네 방향을 다 돌며 순회한다. 이때, 예제의 입력과 달리 사방이 벽이라는 조건은 주어지지 않으므로, 반드시 로봇 청소기가 주어진 인덱스 안에서 순환하도록 조건을 달아줘야 한다.

 

그 다음, 벽이 아니며 동시에 청소하지 않은 곳일 때, 청소해준다. 청소가 가능하므로 cnt를 1 증가시킨다. 그 다음, 그 방향으로 이동해야 하므로 큐에 값을 넣어준다.

 

여기서 하나라도 청소할 곳을 찾는다면 바로 break를 하도록 했다. 그 이유는 아무 곳도 찾지 못한다면 for의 else로 넘어가서 조건을 처리하기 위함이다.

else:  # 4방향 모두 불가능
    if graph[x - dx[d]][y - dy[d]] != 1:
        q.append((x - dx[d], y - dy[d], d))

이제 4 방향 모두가 불가능하다면, 마지막 보루로 후진을 하도록 한다. 이때, 원본 방향을 갖고 있는 변수 d를 통해서 각 값을 빼주면 후진이 가능하다. 그후에 좌표값이 1이 아닐 때만, 그 방향을 유지한 채로 후진한다.

📌 총평

구현이 재밌었다.

 

하지만, 문제에서 주어진 d의 값과 내가 회전할 값을 일치시킨다든가의 세부 조건을 충족하지 못했었고, 그 부분을 나중에 보완하는 것이 필요하다.