[백준/Python] 로봇 청소기

 

https://www.acmicpc.net/problem/14503

 

---

저는 BFS를 사용했습니다.

 

 

현재 칸이 0이면 청소
상하좌우

- 청소 되지 않은 칸이 없으면 한 칸 후진 (벽이면 멈춤)

- 청소 되지 않은 칸이 있으면 반시계 회전 (앞 칸이 청소 안된 곳일 때까지)

반복

 

방문 확인을 위한

: 벽(1)과 청소가 안된 것(0) 청소가 된 것(0.5)로 구분

 

import sys
from collections import deque
input = sys.stdin.readline
# 행 열
n, m = map(int, input().split())
r, c, d = map(int, input().split()) # 0북 1동 2남 3서

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

 

상태

 

    북

서     동

    남

 

# 0북 1동 2남 3서
w = [(-1, 0), (0, 1), (1, 0), (0, -1)]

북쪽으로 간다 -> 위쪽으로 간다  

동쪽으로 간다 -> 오른쪽으로 간다

남쪽으로 간다 -> 아래쪽으로 간다

서쪽으로 간다 -> 왼쪽으로 간다

 

반시계로 회전 -> 현재 방향 인덱스 -1씩 해준다

후진 -> 현재 방향을 뺀다 (북쪽이면 1,0 으로, 동쪽이면 0, -1로)

 

상하좌우가 청소 되지 않은 칸이 있는지 없는지 확인하는 함수

def check(nowx, nowy):
    for dx, dy in w:
        x = nowx + dx
        y = nowy + dy
        if 0<=x<n and 0<=y<m:
            if graph[x][y] == 0:
                return True
    return False

한 칸이라도 청소되지 않은 칸이 있다면 return True

없다면 return False

 

 

def bfs(nowx, nowy,d):
    cnt = 0
    queue = deque([(nowx, nowy)])
    
    while queue:
        nowx, nowy = queue.popleft()
        # 현재 칸 청소
        if graph[nowx][nowy] == 0:
            graph[nowx][nowy] = 0.5
            cnt += 1
            
        if check(nowx, nowy): # 청소 되지 않은 게 있으면
            # 반시계 방향으로 회전
            while True:
                d = d-1 if d>0 else 3
                if graph[nowx+w[d][0]][nowy+w[d][1]] ==0:
                    queue.append((nowx+w[d][0], nowy+w[d][1]))
                    break
        # 후진
        else:
        	# 벽이면 멈춰
            if graph[nowx-w[d][0]][nowy-w[d][1]] == 1:
                break
            # 벽 아니면(청소가 된 칸 0.5면) 후진
            else: 
                x = nowx - w[d][0]
                y = nowy - w[d][1]
                queue.append((x,y))
        print(graph)
    return cnt

 

print(bfs(r,c,d))