[백준🏅5] 14503 - 로봇 청소기 (Python)

Review

시계 반대 방향과 후진을 생각해 내는데 꽤 오래 걸렸다 ..
방향이 있기에 bfs를 사용한다는 것까지가 내 실력이었단 걸 다시 한번 느꼈다.

✨ HOW? 시계 반대 방향으로 turn

(d + 3 ) % 4

✨ HOW? 후진

nx = x - dx[d] 
ny = y - dy[d]

Code

# 240620
'''
방 n*m, 벽 또는 빈칸, 청소기는 바라보는 방향이 있음 

$0$인 경우 북쪽, 
$1$인 경우 동쪽, 
$2$인 경우 남쪽, 
$3$인 경우 서쪽을 바라보고 있는 것이다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
    1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
    2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
    1. 반시계 방향으로 90도 회전한다.
    2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
    3. 1번으로 돌아간다.
'''

from collections import deque

n, m = map(int, input().split())
r, c, d = map(int, input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))

visited = [[False] * m for _ in range(n)]
visited[r][c] = 1
cnt = 1

'''시계 방향'''
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

queue = deque()
queue.append((r,c))

while queue:    
    flag = False
    x, y = queue.popleft()
    
    for _ in range(4):
        d = ( d + 3 ) % 4
        nx = x + dx[d]
        ny = y + dy[d]
        
        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] == 0:
                if not visited[nx][ny]:
                    visited[nx][ny] = True
                    cnt += 1
                    queue.append((nx, ny))
                    flag = True
                    break
                
    if not flag: # 후진
        nx = x - dx[d] 
        ny = y - dy[d]
        if graph[nx][ny] == 1:
            print(cnt)
            break
        else:
            queue.append((nx, ny))
                

시간복잡도

해당 알고리즘의 시간 복잡도는 주어진 맵의 크기에 비례합니다. 
맵의 크기가 N×M일 때, 모든 칸을 한 번씩 방문해야 하므로 
최악의 경우 O(N×M)의 시간 복잡도를 가지게 됩니다.