백준 2178 파이썬(DFS/BFS)

bfs문제다.

최단거리를 찾는 문제는 bfs탐색법을 활용하면 된다.

bfs는 큐 자료구조를 활용하는데 큐에서 한개씩 꺼내서 연결된 노드들을 탐색하면서 큐가 빌때까지 루프를 돌려주면 되는 탐색 알고리즘이다.

 

# 2178 미로 탐색 - 최단거리

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

arrow = [[-1,0],[1,0],[0,-1],[0,1]] # 상하좌우
from collections import deque
def bfs(x,y,step=1):
    q = deque()
    q.append([x,y])
    while q:
        node = q.popleft()
        for i in arrow:
            new_node = [x+y for x,y in zip(node,i)]
            if new_node[0] < 0 or new_node[1] < 0 or new_node[0] > n-1 or new_node[1] > m-1:
                continue 
            if graph[new_node[0]][new_node[1]] == 1:
                q.append(new_node)
                graph[new_node[0]][new_node[1]] = graph[node[0]][node[1]] + 1

bfs(0,0)
print(graph[n-1][m-1])