'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 14503번: 로봇 청소기
1. 문제
- 로봇 청소기가 청소하는 영역 NxM이 주어지며, 각각의 칸은 벽(1) 또는 빈 칸(0)이다.
- 로봇 청소기는 다음과 같이 동작한다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
- 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
- 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
- 로봇 청소기가 처음 위치한 칸의 상태는 항상 빈 칸이다.
- 로봇 청소시가 청소하는 칸의 개수를 출력한다.
2. 풀이
DFS
를 이용한 문제 풀이
- 청소한 곳은 2로 변경
- 왼쪽으로 회전하는 코드 구현
- 회전 후 빈칸일 경우 전진하고 청소한 후 다시 네방향 탐색
- 네방향 탐색 후 뒤가 벽이면 종료, 뒤가 빈 칸이면 다시 뒤로 가고 청소한 후 다시 네방향 탐색
3. 코드
N, M = map(int, input().split())
x, y, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
D = {0:(-1,0), 1:(0,1), 2:(1,0), 3:(0,-1)} # 북동남서
cnt = 1
def solution():
global cnt
def dfs(x, y, d):
global board, N, M, D, cnt
for _ in range(4):
d = (d+3) % 4 # 왼쪽으로 회전하기 위해 +3
nx = x + D[d][0]
ny = y + D[d][1]
if not board[nx][ny]: # 빈 칸일 때
board[nx][ny] = 2 # 2로 변경 (청소)
cnt += 1
dfs(nx, ny, d)
return
if board[x-D[d][0]][y-D[d][1]] == 1: # 뒤가 벽일 경우
return
else:
dfs(x-D[d][0], y-D[d][1], d) # 뒤가 빈 칸일 경우
board[x][y] = 2 # 처음 현재 칸 청소
dfs(x,y,d)
return cnt
print(solution())
- 결과는 64 ms 나왔다.
References
🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋
'Coding Test > BOJ' 카테고리의 다른 글
[백준] 14888 - 연산자 끼워넣기 [Python(파이썬)] (0) | 2021.11.22 |
---|---|
[백준] 14502 - 연구소 [Python(파이썬)] (0) | 2021.11.22 |
[백준] 14501 - 퇴사 [Python(파이썬)] (0) | 2021.11.22 |
댓글