[백준] 14503번 로봇 청소기

💡문제접근

• BFS 완전탐색으로 문제를 접근했다. 문제에서 주어진 흐름대로 코드를 작성해갔고 조금의 시간이 걸렸지만 혼자서 해결할 수 있었다.
• 방문여부를 따지면서 탐색을 진행하는 방법도 있지만 청소를 한 구역을 처리해주는 방식을 구현해주면 방문여부를 따지는 배열을 만들 필요없이 탐색을 성공적으로 수행할 수 있다.

💡코드(메모리 : 34088KB, 시간 : 68ms)

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
# d : 0(북), d : 1(동), d : 2(남), d : 3(서)
r, c, d = map(int, input().strip().split())
graph = [list(map(int, input().strip().split())) for _ in range(N)]

cnt = 0
def BFS(a, b):
    global cnt, d
    queue = deque()
    queue.append([a, b])
    graph[a][b] = -1
    cnt += 1
    while queue:
        # 북, 동, 남, 서
        flag = 0
        dr = [-1, 0, 1, 0]
        dc = [0, 1, 0, -1]
        r, c = queue.popleft()
        for i in range(4):
            d = (d+3) % 4
            nr = r + dr[d]
            nc = c + dc[d]
            if 0 <= nr < N and 0 <= nc < M and graph[nr][nc] == 0:
                queue.append([nr, nc])
                graph[nr][nc] = -1
                cnt += 1
                flag = 1
                break
        # 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
        if flag == 0:
            # 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면? → 한 칸 후진
            if graph[r - dr[d]][c - dc[d]] != 1:
                queue.append([r-dr[d], c-dc[d]])
            # 바라보는 방향을 유지한 채로 한 칸 후진할 수 없다면? → 작동 멈춘다.
            else:
                print(cnt)
                break

BFS(r, c)

💡소요시간 : 45m