[백준] 2178 미로 탐색 - python

- 문제 링크 : https://www.acmicpc.net/problem/2178

- 접근 방법 : 처음엔 이동에 제약이 있는 경우라고 생각해 DFS로 풀었다. 예제 입력은 다 맞았지만 DFS는 모든 노드를 다 탐색하기 때문에 시간이 오래 걸려 런타임 에러가 떴다. 다시 문제를 읽어보니 '지나는 최소 칸 수' 즉 최단거리를 구하는 문제였다. 최단거리는 BFS로 접근해야하고, 인접한 경로의 거리를 업데이트하는 식으로 코드를 작성하였다.

# DFS 사용, 런타임 에러 발생
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
visited[0][0] = 1

dx = [1,-1,0,0]
dy = [0,0,1,-1]
cnt = 0

def dfs(x,y):
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
    
        if 0<=nx<n and 0<=ny<m and graph[nx][ny]==1:
            if visited[nx][ny] == 0 or visited[nx][ny] > visited[x][y] + 1:
                visited[nx][ny] = visited[x][y] + 1
                if nx == n-1 and ny ==m-1:
                    return
                dfs(nx,ny)
    return

dfs(0,0)
print(visited[n-1][m-1])

# BFS 사용, 모든 노드를 방문하는 것이 아니기 때문에 시간 적게 소요됨
from collections import deque

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

dx = [1,-1,0,0]
dy = [0,0,1,-1]
cnt = 0

def bfs(x, y):
    q = deque([(x,y)])
    visited[x][y] = 1

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
			
            # if문 하나에서 여러 조건을 확인하는 것 보다 아래처럼 쪼개는 것이 속도가 빠름
            if 0<=nx<n and 0<=ny<m and graph[nx][ny]==1: 
                if visited[nx][ny] == 0 or visited[nx][ny] > visited[x][y] + 1:
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
    return