로봇 청소기
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 방은
NxM 크기의 직사각형으로 나타낼 수 있으며, 1x1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r, c)는 북쪽에서
(r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.
로봇 청소기는 다음과 같이 작동한다.
현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우, 반시계 방향으로 90도 회전한다.
바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
1번으로 돌아간다.
입력
출력
import sys
from collections import deque
sys.stdin = open("input.text", "rt")
n,m = map(int, input().split())
x,y,d = map(int, input().split()) #청소기 시작위치, 처음 바라보는 방향
#d가 0:북, 1:동, 2:남, 3:서
g = [list(map(int, input().split())) for _ in range(n)] #nxm 보드판
#0이면 청소하지 않은 빈칸, 1이면 벽
#멈출 때까지 청소하는 칸의 개수
ch = [[0] * m for _ in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1] #북 동 남 서 순으로 방향벡터 적용
cnt = 0
while True:
if g[x][y] == 0 and ch[x][y] == 0:
ch[x][y] = 1 #방문처리 -> 방문한 빈칸
cnt += 1
flag = False
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if g[nx][ny] == 0 and ch[nx][ny] == 0:
flag = True
#청소되지 않은 빈칸 존재
break
if flag == False: #방문 불가면 후진
temp = (d + 2) % 4 #바라보는 방향은 유지.
tx = x + dx[temp]
ty = y + dy[temp]
if 0<=tx<n and 0<=ty<m and g[tx][ty] == 0: #후진 가능 방문했는지는상관없음.
x,y = tx,ty
continue
else:
break
else: #방문 가능
d = (d+3) % 4 #반시계 이동후
tx = x + dx[d]
ty = y + dy[d]
if 0<=tx<n and 0<=ty<m and g[tx][ty] == 0 and ch[tx][ty] == 0:
x,y = tx,ty
print(cnt)
⚽ 코멘트
전형적인 구현 문제.
문제에서 요구하는 내용을 오류없이 구현만 할 수 있었으면 됐다.
😀 방향을 설정해서 이동하는 문제 유형은 dx,dy의 방향벡터를 설정해서 이끌어 나가자.
문제를 제대로 이해했어야 했다. 현재 방향 기준으로 반시계 -> 왼쪽부터 탐색한다.
💨 여기서 내가 실수한 것은 그래프 내에서 빈칸을 방문하면 그곳을 벽으로 만들어 버렸다는 것이다. 사실 따로 방문 리스트를 만들었어야만 했다. 청소했더라도 후진을 할 수 있었어야 했기 떄문...
👻 내가 실수한 부분
- 문제에서 따로 중복을 체크하는 리스트를 만들어놓고 가장 처음에 "방문하지 않은 빈칸"을 확인했어야 했는데 체크 리스트는 적용하지 않았다... 이게 문제였다.
