[이것이 코딩 테스트다] 실전 문제 5-4 미로 탈출

교재에 서술된 정답 코드가 아닌, 제가 직접 작성한 코드입니다.

---

• 최소 이동 칸을 구하기 위한 것이므로 오른쪽 이동과 아래쪽 이동만 고려하면 된다.
• 만약 어떤 칸의 오른쪽과 왼쪽에 모두 괴물이 있다면 해당 칸으론 더 이상 이동할 수 없으므로, count에서 -1 해야 한다.
  • 다만 마지막 칸의 경우에는 j + 1 < m과 i + 1 < n 때문에 flag가 True라서 count - 1 되므로, return 시 count에 1을 더해주어야 한다.

from collections import deque

def solution(x, y):
    graph[x][y] = 0

    queue = deque([(x, y)])
    count = 0
    while queue:
        i, j = queue.popleft()
        count += 1

        flag = True
        if j+1 < m and graph[i][j+1]:
            flag = False
            queue.append((i, j+1))

        if i+1 < n and graph[i+1][j]:
            flag = False
            queue.append((i+1, j))

        if flag:
            count -= 1

    return count + 1 # 마지막 칸일 때도 -1 되기 때문에 count + 1 해야 한다.

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

print(solution(0, 0))