백준 - 미로찾기 / Silver 1 / 2178번 / Python

문제 📋

백준 - 미로찾기

시간초과 풀이 📝

import sys


def dfs(start):
    global cnt
    delta_row = [1, -1, 0, 0]
    delta_col = [0, 0, 1, -1]

    row, col = start
    visited[row][col] = True
    cnt += 1

    if row == N-1 and col == M-1:
        answer.append(cnt)
        return

    for i in range(4):
        next_row = row + delta_row[i]
        next_col = col + delta_col[i]

        if 0 <= next_row < N and 0 <= next_col < M and maze[next_row][next_col] == 1 and not visited[next_row][next_col]:
            dfs((next_row, next_col))
            visited[next_row][next_col] = False
            cnt -= 1
    return


N, M = map(int, sys.stdin.readline().split())
maze = [list(map(int, list(sys.stdin.readline())[:-1])) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
answer = []

global cnt
cnt = 0

dfs((0, 0))

print(min(answer))

올바른 풀이 📝

import sys
from collections import deque


def solution(N, M, maze):
    breadth = 1
    delta_row = [1, -1, 0, 0]
    delta_col = [0, 0, 1, -1]
    visited = [[False] * M for _ in range(N)]
    q = deque([(0, 0)])

    while q:
        for _ in range(len(q)):
            row, col = q.popleft()

            if row == N - 1 and col == M - 1:
                return breadth

            for i in range(4):
                next_row = row + delta_row[i]
                next_col = col + delta_col[i]

                if next_row < 0 or next_row > N-1 or next_col < 0 or next_col > M-1:
                    continue

                if visited[next_row][next_col]:
                    continue

                if maze[next_row][next_col] == 1:
                    q.append((next_row, next_col))
                    visited[next_row][next_col] = True
        breadth += 1


N, M = map(int, sys.stdin.readline().split())
maze = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]

print(solution(N, M, maze))

처음에는 DFS로 문제에 접근했다.
하지만 DFS는 최단거리가 보장되지 않기 때문에
DFS로 탐색할 수 있는 모든 경로를 다 찾고 거기서 가장 작은 count 값을 찾아야 했다.

N, M의 값이 최대 100이므로 최악의 경우를
생각하면 모든 경로를 탐색한다는 것은 불가능에 가깝다.
당연하게도 시간 초과가 났다.

따라서 BFS로 문제를 다시 접근했다.
사실 최단거리 하면 바로 BFS를 떠올려야 되지만
칸수를 어떻게 세야 할지 처음엔 감이 잘 오지 않았다.

고민해 본 결과 길을 한 칸 앞으로 진행한다는 것의 의미는
바로 이번 breadth 탐색을 끝내고 다음 breadth으로 나아간다는 것이다.
따라서 (N-1, M-1) 칸에 도달했을 때
몇 번째 breadth 인지만 체크해 주면 그것이 바로 최단 경로이다.