[알고리즘] 로봇청소기 - bfs

문제

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

14503번: 로봇 청소기

 

생각할 점 [ 문제풀이 ]

1. 처음 주워지는 방향을 통해서 반시계 방향으로 회전시키는 것 주의 ( 방향 전환이 어려울 수 있음 )

2. 전진하지 못하는 경우 주의 [ can_go 메소드 보기 ]

3. 만약에 4가지 방향 ( 반시계 방향 )으로 전부 돌았지만 청소한 영역이 없다면 후진할텐데, 주의할점은 처음에 후진하는 공간이 범위 내에 있나를 체크 못했었는데, 이 점을 주의 하자

 

코드

import sys
from collections import deque

n,m = map(int,input().split())
x,y,d = map(int,input().split())

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

visited = [
    [False for _ in range(m)]
    for _ in range(n)
]

# 북 동 남 서 (상 우 하 좌)
dxs,dys = [-1,0,1,0],[0,1,0,-1]
q = deque()

visited[x][y] = True
q.append((x,y,d))

ans = 0

def can_go(nx,ny): # 회전시키기
    return in_range(nx,ny) and arr[nx][ny] == 0 and not visited[nx][ny]

def cntClean():
    global ans
    for i in range(n):
        for j in range(m):
            if visited[i][j]:
                ans += 1

def in_range(x,y):
    return 0<=x<n and 0<=y<m

def bfs():

    while q:
        x,y,d = q.popleft()

        for _ in range(4):
            d = (d+3) %4
            nx,ny = x + dxs[d], y + dys[d]

            if not can_go(nx,ny):
                continue

            visited[nx][ny] = True
            q.append((nx,ny,d))
            break

        else:
            temp_d = (d+2) % 4
            nx,ny = x + dxs[temp_d], y + dys[temp_d]
            
            if not in_range(nx,ny) or arr[nx][ny]:
                return
            
            q.append((nx,ny,d))

        

bfs()
cntClean()
print(ans)