[알고리즘] 백준 2178번 미로 탐색 (Python)

728x90

DFS / BFS

문제

문제링크

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

풀이

원래 DFS로 풀려고 했다가, 최소 칸의 수를 구하려면 어떻게 해야 할지 모르겠어서 찾아봤다.
그러나, DFS로 최소 이동 칸 수를 구하는 건 비효율적이라는 답을 얻었다.
왜냐하면 DFS는 깊이 우선 탐색이라 한 방향으로 쭉 가다가 되돌아와야 할 때 너무 많은 경로를 탐색하게 되기 때문이다.

이런 경우에는 BFS(너비 우선 탐색)이 훨씬 좋다고 한다.
왜냐하면 BFS는 가까운 거리부터 탐색하기 때문에 먼저 도착하는 경로가 최단 거리가 되기 때문이다!

그래서 BFS로 최소 이동 칸 수를 구했다.

BFS 이용 풀이

큐(queue)를 사용해 탐색을 진행 (FIFO 방식)
시작 위치에서 상하좌우 이동하면서 탐색
방문한 곳은 다시 방문하지 않도록 체크
목표 지점에 도착하면 이동 거리 출력

CODE

1) visited 배열 사용

처음에는 습관처럼 visited 배열을 사용해서 방문한 지점을 체크했다.
이때 유의할 점은, 큐에 넣기 전에 방문을 체크해야 한다는 점이다!

# 2178번. 미로 탐색

import sys
import collections
input = sys.stdin.readline

N, M = map(int, input().split())
mymap = [[int(i) for i in input().rstrip()] for _ in range(N)]

visited = [[False] * M for _ in range(N)]

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

def bfs(r, c):
    que = collections.deque()
    que.append((r, c, 1))   # 시작점 큐에 추가
    
    visited[r][c] = True    # 시작점 방문 표시
    
    while que:
        y, x, dist = que.popleft()  # 현재 위치 및 이동 거리
        
        if y == N-1 and x == M-1:
             return dist
         
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0 <= ny < N and 0 <= nx < M and not visited[ny][nx] and mymap[ny][nx] == 1:
                visited[ny][nx] = True  # 큐에 넣기 전에 방문 체크
                que.append((ny, nx, dist+1))

print(bfs(0, 0))

2) visited 배열 사용 대신 mymap 배열 자체에 거리 계산 적용

이전 풀이를 보니, visited를 사용하지 않고 원래 있던 배열에 거리 계산을 추가하는 식으로 풀이했었던 걸 보고, 이 방식으로 풀이해보았다.

이렇게 mymap 자체를 업데이트하면서 방문 여부를 표시하면 메모리를 절약할 수 있다.

mymap[nr][nc]가 1이면 아직 방문하지 않은, 갈 수 있는 경로이므로 이런 식으로 방문 여부를 확인할 수 있다.

추가로, dfs/bfs 문제를 풀 때마다 x, y가 헷갈려서 그냥 r, c로 통일하도록 바꿨다. (r: 행, c: 열)

# 2178번. 미로 탐색

import sys
import collections
input = sys.stdin.readline

n, m = map(int, input().split())
mymap = [[int(i) for i in input().rstrip()] for _ in range(n)]

# 상하좌우
dr = [1, -1, 0, 0]
dc = [0, 0, -1, 1]

def bfs(r, c):
    que = collections.deque([(r, c)])
    
    while que:
        r, c = que.popleft()  # 현재 위치 및 이동 거리
         
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            
            if 0 <= nr < n and 0 <= nc < m and mymap[nr][nc] == 1:
                mymap[nr][nc] = mymap[r][c] + 1     # 거리 계산
                que.append((nr, nc))
    
    return mymap[n-1][m-1]

print(bfs(0, 0))

결과

먼저 제출한 것이 1번 풀이, 나중에 제출한 것이 2번 풀이다.

나중에 제출한 것이 메모리도 적게 쓰고, 더 빠르고, 코드 길이도 간결하다.