문제
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
로봇 청소기는 다음과 같이 작동한다.
-
현재 위치를 청소한다.
-
현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
접근 방법
시간을 들여서 잘 생각해 보면 충분히 풀 수 있는 문제였던 것 같다.
사실 설명이랄 것도 없을 것 같다. 문제에서 제시해준 대로 따라서 그대로 구현을 하면 된다.
- 왼쪽부터 차례대로 탐색
a. 해당 방이 벽 혹은 청소된 곳인지 아닌지 판별
b. 청소해야할 방이라면 해당 방을 체크하고 로봇 이동
c. 위 과정 반복 - 후진 판별
a. 4방향이 청소가 필요 없을 때 뒤에 벽이 있는지 없는지 판별
b. 벽이 있다면 끝/ 아니라면 로봇 후진
이런 식으로 생각하고 코드를 구현했다.
중요한 점은 왼쪽부터 탐색할 때 방향을 맞춰주는 것,
후진할때 방향 및 좌표를 맞춰주는 것 정도?
코드
N, M = map(int, input().split())
r, c, d = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(N)]
dir = [[0,-1],[-1,0],[0,1],[1,0]]
back = [[1,0],[0,-1],[-1,0],[0,1]]
cnt = 0
st = [(r, c, d)]
while st:
# 현재 위치와 방향 받기
r, c, d = st.pop()
# 현재 위치가 청소해야할 방이면 cnt 올리고 체크
if room[r][c] == 0:
cnt += 1
room[r][c] = 2
# tmp는 4방향이 모두 벽 혹은 청소된 방인지를 판별
tmp = 0
# 4방향 탐색(왼쪽부터( (d+3)%4로 방향 맞추기))
for i in range(4):
nr = r + dir[d][0]
nc = c + dir[d][1]
# 바라본 방향이 청소해야할 방이라면
if 0 <= nr < N and 0 <= nc < M and room[nr][nc] == 0:
# 스택에 추가 후 반복문 종료
st.append((nr, nc, (d+3)%4))
break
# 벽 혹은 청소된 방이라면 tmp 증가
if room[nr][nc] == 1 or room[nr][nc] == 2:
tmp += 1
# 로봇의 바라보는 방향 조정
d = (d+3) % 4
# 4방향이 벽 혹은 청소된 방이고 후진 가능하면 스택에 추가
# 아니라면 그냥 while문 종료
if tmp == 4 and room[r + back[d][0]][c + back[d][1]] == 2:
st.append((r + back[d][0], c + back[d][1], d))
elif tmp == 4:
break
print(cnt)