[BOJ/백준] 14503번 PYTHON

문제

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

유형

DFS

배운 점

전형적인 dfs 문제

풀이법

문제에서 제시한대로 구현하면 된다

1. 현재 칸이 벽(1)이 아니고, 청소 되지 않았을 시(2가 아닐 시)에 0을 2로 바꿔준다
   1-1. 현재 칸 주변에 0이 있을 시 반시계 방향으로 방향을 바꿔가며 0을 향하게끔 방향을 맞추고 한칸 이동한다
   1-2. 현재 칸 주변에 0이 없을 시 본래 바라보던 방향으로 한칸 후진한다

종료 조건 : 후진 시에 벽일 시(1일 시) 동작을 멈춘다

코드

from collections import deque

rx = [-1,0,1,0]
ry = [0,1,0,-1]


r, c = map(int, input().split())
sx, sy, rn = map(int, input().split())

stack = deque([])
stack.append((sx,sy))
graph = []
for _ in range(r):
    graph.append(list(map(int , input().split())))
count = 0

while True:
    if stack:
        (x, y) = stack.pop()

        # x, y가 벽이 아닐 때
        if x >= 0 and y >= 0 and x < r and y < c and graph[x][y] != 1:
            # x, y가 청소하지 않은 칸일 때
            if graph[x][y] == 0:
                # x, y 칸 청소
                graph[x][y] = 2
                count += 1

            flag = False
            # 현재 바라보는 위치에서 반시계 방향으로 청소 안된 칸 확인
            for i in range(1, 5):
                dn = (rn - i + 8)  % 4
                # 청소 안된 칸 존재 시에 한칸 전진 (스택에 삽입)
                if x+rx[dn] >= 0 and y+ry[dn] >= 0 and x+rx[dn] < r and y+ry[dn] < c:
                    if graph[x+rx[dn]][y+ry[dn]] == 0:
                        stack.append((x+rx[dn],y+ry[dn]))
                        rn = dn
                        flag = True
                        break
            # 청소 안된 칸이 없을 시 기존 바라보는 방향에서 후진
            if not flag:
                stack.append((x-rx[rn],y-ry[rn]))            
        # x, y가 벽일 때
        else:
            break

print(count)