236. 로봇 청소기

아현·2021년 8월 6일
0

Algorithm

목록 보기
246/400
post-custom-banner

백준




1. Python



import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
#r,c, d(동,서,남,북)
r, c, d = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]

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

def bfs(x, y, d):
    count = 1
    q = deque()
    q.append((x, y, d))
    data[x][y] = 2
    while q:
        x, y, d = q.popleft()
        cur = d
        for i in range(4):
            cur = (cur - 1) % 4 #왼쪽 방향부터
            nx = x + dx[cur]
            ny = y + dy[cur]
            
            if 0 <= nx < n and 0 <= ny < m and data[nx][ny] == 0: #왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행
                count+= 1
                data[nx][ny] = 2
                q.append((nx, ny, cur))
                break
            
            elif i == 3: 
                cur = (d + 2) % 4
                nx = x + dx[cur]
                ny = y + dy[cur]

                if data[nx][ny] == 1: #네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
                    return count
                else: #네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
                    q.append((nx, ny, d))
    return count
            
print(bfs(r, c, d))


profile
For the sake of someone who studies computer science
post-custom-banner

0개의 댓글