[백준] 14503 로봇청소기 Python

[백준] 14503 로봇청소기 Python

전형적인 구현 문제인데 조건이 조금 까다롭고 방향성을 고려해야하는 문제이다. 또한, 이 문제가 BFS를 사용해야 하는 이유는 여러 방향을 다 탐색하기 때문이다.

먼저,로봇 청소기의 방향은 북,동,남,서 순으로 0,1,2,3이다.
먼저,4칸을 for문을 통해 둘러보고 청소되지 않은 빈칸이 있는 경우 반시계 방향 90도 회전해야한다.

반시계 방향 회전?
(d+3)%4를 해주면 된다.

바라보는 방향 기준으로 앞쪽 칸이 청소되지 않는 쪽으로 전진한다.
tmp_d를 두어서 현재 방향을 저장해놔야 한다. 또, 하나 주의해야하는 점은!전진한 경우 반복문에서 꼭! break를 걸어줘야 한다. 그 이유는 최단거리를 찾는 문제가 아니라 청소되지 않는 곳을 찾았으면 다시 1번으로 돌아가서 반복해줘야 하기 때문이다.

만약, 현재 칸 주변 4칸 중 청소되지 않는 빈칸이 없는 경우(벽이거나 모두 청소 되었음)는 바라보는 방향을 유지하고 후진해야한다. 후진할 수 있으면!만약 후진 못하면 종료해야함!

import sys
sys.stdin=open("input.txt")
from collections import deque

n,m=map(int,input().split())
r,c,d=map(int,input().split())
graph=[]
for _ in range(n): #1이 벽, 0이 빈칸
    graph.append(list(map(int,input().split())))

#0=북,1=동,2=남,3=서
dx=[-1,0,1,0]
dy=[0,1,0,-1]

def bfs(si,sj,d):
    q=deque()
    q.append((si,sj,d))
    cnt=1
    graph[si][sj]=2

    while q:
        x,y,d=q.popleft()
        check=0
        tmp_d=d #방향이 바뀔 수 있기 때문에 원래의 방향 유지!

        for _ in range(4): #주변 탐색
            nd=(tmp_d+3)%4 #반시계방향으로 돌기
            nx=x+dx[nd]
            ny=y+dy[nd]
            tmp_d=nd #회전방향 업데이트

            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny]==0: #청소되지 않는 방이 있다
                    graph[nx][ny]=2
                    cnt+=1
                    q.append((nx,ny,nd))
                    break #1칸 전진한 칸에서 다시 검사해야한다!그 후로 진행됨

                else: #청소되어 있거나 벽인 경우
                    check+=1


        if check == 4:  # 현재 위치에서 4방향 모두 청소되어 있거나 벽이다
            if graph[x + dx[(d + 2) % 4]][y + dy[(d + 2) % 4]]==1: #후진하는 곳이 벽이다.
                return cnt
            else:
                q.append((x + dx[(d + 2) % 4], y + dy[(d + 2) % 4], d))



print(bfs(r,c,d))