14503 - 로봇 청소기
📌 문제
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
로봇 청소기는 다음과 같이 작동한다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
📋 코드
from collections import deque
def turn_left(d):
return (d - 1) % 4
def go_back(d):
return (d + 2) % 4
def cleaning(r, c, d, grid):
global result
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
q = deque()
q.append((r, c))
grid[r][c] = '#'
result += 1
while q:
x, y = q.popleft()
for i in range(4):
d = turn_left(d)
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < N and 0 <= ny < M and grid[nx][ny] == 0:
grid[nx][ny] = '#'
q.append((nx, ny))
result += 1
break
if i == 3:
nd = go_back(d)
nx, ny = x + dx[nd], y + dy[nd]
if grid[nx][ny] == 1:
return
q.append((nx, ny))
N, M = map(int, input().split())
r, c, d = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(N)]
result = 0
cleaning(r, c, d, grid)
print(result)💡 한마디
구현 문제를 오랜만에 풀어서 그런지 생각보다 푸는 데 오래 걸렸다.
