백준 문제 중 14503번, 구현, ‘로봇 청소기’
문제
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
로봇 청소기는 다음과 같이 작동한다
1.현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
- 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
- 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
입력
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
출력
로봇 청소기가 청소하는 칸의 개수를 출력한다.
풀이
방향이 바뀌는 조건이 조금 까다로웠지만 다음 방향만 잘 조작해준다면 꽤나 쉬운 문제였던것같다.
문제에서 주어진 조건에따라 이동하는 방향과 회전하는 방향을 생각해보자. a조건은 왼쪽에 청소할 수 있는 영역이 있으면 왼쪽으로 회전과 이동을 동시에 수행하고, b 조건은 왼쪽으로 회전만을 , c 조건은 후진으로 이동만을, 그리고 d 조건이라면 종료를한다.
이동과 회전의 동작을 따로 생각하고 왼쪽으로 이동과 뒤쪽으로의 이동을 분리하여 생각해보자
- 진행조건
- 현재 방향을 기준으로 왼쪽방향을 계산한다. 만약 청소가능 구역이 있다면 왼쪽으로 이동하고 탐색을 진행한다.
- 청소가능 구역이 없다면 최신화된 방향을 기준으로 탐색을 진행한다.
- 네 방향 모두 청소가 이미 되어 있거나 벽인 경우에는, 한칸 후진하고 탐색을 진행한다.
- 종료조건
- 네 방향 모두 청소가 이미 되어 있거나 벽이면서, 방향 기준 뒤에가 벽이라면 종료한다.
현재 방향을 기준으로 왼쪽과 뒤쪽 방향을 나타낼 딕셔너리 left, back을 활용했다. 현재방향에 대해 각각 왼쪽과 뒤쪽을 나타낸다.
# 입력처리
n, m = map(int, input().split())
r, c, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
# 좌표를 조작할 dir 선언
dir = {0: [-1, 0], 1: [0, 1], 2: [1, 0], 3: [0, -1]}
# 현재 방향을 기준으로 왼쪽과 뒤쪽 방향을 저장할 딕셔너리 선언
left = {0: 3, 1: 0, 2: 1, 3: 2}
back = {0: 2, 1: 3, 2: 0, 3: 1}
# 네방향이 모두 청소가 이미 되었거나 벽인 경우를 판단할 함수 선언
def is_clear_around(row, col):
for i in range(4):
r, c = row + dir[i][0], col + dir[i][1]
if board[r][c] == 0:
return False
return True
# 스택을 활요해 DFS를 실행할 함수 선언
def dfs(r, c, d):
s = [[r, c, d]]
cnt = 0
while s:
r, c, d = s.pop()
# 스택에서 꺼낸후 board[r][c] 가 2가 아니라면 청소를하고 cnt를 1증가
if board[r][c] != 2:
cnt += 1
board[r][c] = 2
# 왼쪽부분을 탐색
lr, lc = r + dir[left[d]][0], c + dir[left[d]][1]
# 왼쪽이 청소가 안되었다면 이동후 새로운 탐색 진행
if board[lr][lc] == 0:
s.append([lr, lc, left[d]])
continue
else:
br, bc = r + dir[back[d]][0], c + dir[back[d]][1]
# 네 방향의 조건을 만족할때
if is_clear_around(r, c):
# 뒤에마저 벽이라면 종료
if board[br][bc] == 1:
return cnt
# 뒤가 벽이 아니라면 후진 후 새로운 탐색 진행
else:
s.append([br, bc, d])
continue
# 네 방향의 조건은 만족하지 못하고 왼쪽이 청소가 불가능하다면 회전만 하고 진행
else:
s.append([r, c, left[d]])
print(dfs(r,c,d))
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
57
Leave a comment