2178번: 미로탐색

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

 

BFS 아니면 DFS를 사용하겠지 했는데, 최단 경로는 BFS를 사용하는 게 좋겠다 해서 BFS를 사용하기로 했다.

 

BFS를 사용하기 위해 각 리스트 요소를 노드라고 생각하기로 했고 collections 라이브러리의 defaultdict을 사용하여 graph를 만들었다. Undirected Graph이기 때문에 연결되어 있다면 모두 넣어줬다.

# graph 생성
graph = defaultdict(list)
for n in range(N) :
    for m in range(M) :
        if n - 1 >= 0 :
            if maze[n-1][m] == '1' :
                graph[(n, m)].append((n-1, m)) # 상
        if n + 1 < N :
            if maze[n+1][m] == '1' :
                graph[(n, m)].append((n+1, m)) # 하
        if m - 1 >= 0 :
            if maze[n][m-1] == '1' :
                graph[(n, m)].append((n, m-1)) # 좌
        if m + 1 < M :
            if maze[n][m+1] == '1' :
                graph[(n, m)].append((n, m+1)) # 우

 

다음 고민거리는 최단 거리 구하기였다. https://www.acmicpc.net/problem/24444 여기의 알고리즘을 참고하여 BFS를 구현했다.

BFS로 노드 탐색은 되는데, 최단 거리 구하는 것이 문제였다. 그러던 와중 https://wonderwalls.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B2%8C%EC%9E%84-%EB%A7%B5-%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC%ED%8C%8C%EC%9D%B4%EC%8D%AC-DFS-BFS

프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)

위의 글에서 queue에 들어가는 게 노드 정보 뿐만 아니라 거리 정보를 넣는 것을 보고 튜플 형식으로 같이 넣어주었다.

 

# BFS 코드
def bfs(graph, start) :
    ans = defaultdict(int)
    visited = [[0] * M for _ in range(N)]
    visited[0][0] = 1
    q = deque([(start, 1)])
    while q :
        u = q.popleft()
        for v in graph[u[0]] :
            if visited[v[0]][v[1]] == 0 :
                visited[v[0]][v[1]] = 1
                q.append((v, u[1] + 1))
                ans[v] = u[1] + 1
    print(ans[(N-1, M-1)])

BFS는 목표인 N-1, M-1까지 탐색하는 것이 아닌 연결된 곳 중 가장 마지막까지 탐색하므로, 목표 노드까지의 거리를 측정하는 것이 필요하여 ans라는 defaultdict을 생성해서 노드 정보를 key로, 거리 정보를 value로 주어 바로 출력할 수 있도록 했다.

 

# 전체 코드

# https://www.acmicpc.net/problem/2178
import sys
from collections import deque, defaultdict

# inputs
N, M = map(int, sys.stdin.readline().split())
maze = []
for _ in range(N) :    
    maze.append(sys.stdin.readline().split()[0])

# graph 생성
graph = defaultdict(list)
for n in range(N) :
    for m in range(M) :
        if n - 1 >= 0 :
            if maze[n-1][m] == '1' :
                graph[(n, m)].append((n-1, m)) # 상
        if n + 1 < N :
            if maze[n+1][m] == '1' :
                graph[(n, m)].append((n+1, m)) # 하
        if m - 1 >= 0 :
            if maze[n][m-1] == '1' :
                graph[(n, m)].append((n, m-1)) # 좌
        if m + 1 < M :
            if maze[n][m+1] == '1' :
                graph[(n, m)].append((n, m+1)) # 우
         
# BFS 코드
def bfs(graph, start) :
    ans = defaultdict(int)
    visited = [[0] * M for _ in range(N)]
    visited[0][0] = 1
    q = deque([(start, 1)])
    while q :
        u = q.popleft()
        for v in graph[u[0]] :
            if visited[v[0]][v[1]] == 0 :
                visited[v[0]][v[1]] = 1
                q.append((v, u[1] + 1))
                ans[v] = u[1] + 1
    print(ans[(N-1, M-1)])

bfs(graph, (0, 0))