[백준] 14503 - 로봇 청소기 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀

문제 👉 14503번: 로봇 청소기

1. 문제

1. 로봇 청소기가 청소하는 영역 NxM이 주어지며, 각각의 칸은 벽(1) 또는 빈 칸(0)이다.
2. 로봇 청소기는 다음과 같이 동작한다.
   1. 현재 위치를 청소한다.
   2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
      • 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
      • 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
      • 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
      • 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
3. 로봇 청소기가 처음 위치한 칸의 상태는 항상 빈 칸이다.
4. 로봇 청소시가 청소하는 칸의 개수를 출력한다.

2. 풀이

DFS를 이용한 문제 풀이

1. 청소한 곳은 2로 변경
2. 왼쪽으로 회전하는 코드 구현
3. 회전 후 빈칸일 경우 전진하고 청소한 후 다시 네방향 탐색
4. 네방향 탐색 후 뒤가 벽이면 종료, 뒤가 빈 칸이면 다시 뒤로 가고 청소한 후 다시 네방향 탐색

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

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋