파이썬 로봇 청소기(BOJ 14503)
문제
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 방은 N x M 크기의 직사각형으로 나타낼 수 있으며, 1×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)$이다. 즉, 좌표(r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.
로봇 청소기는 다음과 같이 작동한다.
- 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
- 반시계 방향으로 90∘ 회전한다.
- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
- 1번으로 돌아간다.
입력
첫째 줄에 방의 크기 N과 M이 입력된다. (3≤N,M≤50) 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.
셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N x M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 1인 경우 (i, j)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.
출력
로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.
예제 입력 1
3 3
1 1 0
1 1 1
1 0 1
1 1 1
예제 출력 1
1
예제 입력 2
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
예제 출력 2
57
📝 풀어보기
방의 크기 N, M을 입력받는다. 로봇의 초기 위치는 r(세로), c(가로), d(방향)이다.
dx, dy에는 로봇의 이동 방향을 저장한다.
room에는 방의 상태를 저장한다. 0은 빈 칸, 1은 벽, 2는 청소를 한 칸으로 나타냈다.
visited는 해당 위치의 방문여부를 확인하기 위해 사용한다.
초기에 로봇은 r, c의 좌표에서 시작한다. 그리고 해당 위치는 항상 0으로 되어있다. 그러므로 해당 위치는 청소를 한 것으로 처리하고 카운트를 1로 저장해둔다.
from pprint import pprint
N, M = map(int, input().split())
# d = 0 북, 1 동 2 남 3 서
r, c, d = map(int, input().split())
# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# d = (d+3) % 4 왼쪽으로 회전
# 3, 2, 1, 0 서 남 동 북
# [r - dx[dir]][c - dy[dir]] 후진
room = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
room[r][c] = 2
cnt = 1
회전에 대한 함수를 정의해둔다.
문제에서 d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 나타낸다.
로봇은 장애물을 만나면 90도 왼쪽으로 회전한다. 즉, 북쪽(0)을 보고있다가 장애물을 만나면 서쪽(3), 동쪽(2)를 보고있다가 장애물을 만나면 북쪽(0)을 바라본다. 이것을 공식으로 만들 수 있는데, 이 때 dx, dy의 배치 순서 또한 중요하다.
# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# d = (d+3) % 4 왼쪽으로 회전
북쪽을 바라보다가 장애물을 만났다면? (0+3) % 4 = 3
dx, dy의 3번째 인덱스는 서쪽을 바라본다.
동쪽을 바라보다가 장애물을 만났다면? (1+3) % 4 = 0
dx, dy의 0번째 인덱스는 북쪽을 바라본다.
# 왼쪽으로 회전시킨다.
def turn(d):
d = (d+3) % 4
return d
# 3, 2, 1, 0 서 남 동 북
print((0+3) % 4) = 3
print((1+3) % 4) = 0
print((2+3) % 4) = 1
print((3+3) % 4) = 2
이와 같은 방법으로 로봇의 회전을 구현할 수 있다.
로봇의 움직임과 청소를 하는 robot함수를 정의한다.
- 인자로 들어온 현재칸이 청소되지 않은 경우에 현재칸을 청소하고 cnt를 1 증가시킨다.
- 방을 벗어나지 않는 범위에서 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
- 반 시계 방향으로 90도 회전한다.
- 바라보는 방향을 기준으로 청소되지 않은 칸이 있다면 전진하고 1번을 반복한다.
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
- 바라보는 방향을 유지한채 한 칸 후진할 수 있으면 후진하고()(dir+2) % 4) 1번을 반복한다.
- 바라보는 방향의 뒷칸이 벽이라 후진 할 수 없다면 작동을 멈춘다.
def robot(x, y, dir):
global cnt
if room[x][y] == 0:
room[x][y] = 2
cnt += 1
for _ in range(4):
nd = turn(dir)
nx = x + dx[nd]
ny = y + dy[nd]
if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
if not visited[nx][ny]:
robot(nx, ny, nd)
return
dir = nd
nd = (dir+2) % 4
nx = x + dx[nd]
ny = y + dy[nd]
if room[nx][ny] == 1:
return
robot(nx, ny, dir)
robot(r, c, d)
print(cnt)
전체코드
from pprint import pprint
N, M = map(int, input().split())
# d = 0 북, 1 동 2 남 3 서
r, c, d = map(int, input().split())
# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# d = (d+3) % 4 왼쪽으로 회전
# 3, 2, 1, 0 서 남 동 북
# [r - dx[dir]][c - dy[dir]] 후진
room = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
room[r][c] = 2
cnt = 1
# 왼쪽으로 회전시킨다.
def turn(d):
d = (d+3) % 4
return d
# 1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
# 2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
# 1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
# 2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
# 3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
# 1. 반시계 방향으로 90도 회전한다.
# 2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
# 3. 1번으로 돌아간다.
def robot(x, y, dir):
global cnt
if room[x][y] == 0:
room[x][y] = 2
cnt += 1
for _ in range(4):
nd = turn(dir)
nx = x + dx[nd]
ny = y + dy[nd]
if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
if not visited[nx][ny]:
robot(nx, ny, nd)
return
dir = nd
nd = (dir+2) % 4
nx = x + dx[nd]
ny = y + dy[nd]
if room[nx][ny] == 1:
return
robot(nx, ny, dir)
robot(r, c, d)
print(cnt)