BFS (Breadth-First Search)

BFS -> Queue 이용

위 코드에서 큐에서 꺼낸 노드의 인접한 노드들 부터 넓은 방향으로 방문하다가 모든 노드를 방문하여 큐에 남은 노드가 없을 때 반복을 종료한다.

문제 설명

문제 검토

장애물을 피하여 최단 경로를 찾는 문제이다.
BFS를 떠올려서 누적되는 거리를 계산하는 방법을 떠올리자.

풀이

from collections import deque

def BFS(x,y):
    q=deque()
    q.append((x,y))        

    #큐가 빌 때까지 반복
    while q:
        #큐에서 검사할 노드를 꺼낸다.
        x,y = q.popleft()
        #인접한 4방향 모두 검사
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            #범위 초과시 
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            #장애물이 있을시
            if graph[nx][ny]==0:
                continue
            #처음 방문한 노드라면
            if graph[nx][ny]==1:
                graph[nx][ny]+=graph[x][y]
                q.append((nx,ny))
                
    return(graph[n-1][m-1])
            

n,m=map(int,input().split())
graph=[list(map(int,input())) for x in range(n)]
#상하좌우 방향벡터
dx=[-1,1,0,0]
dy=[0,0,-1,1]

print(BFS(0,0))
    

인접한 노드들을 방문했을 때 현재 노드의 값을 더 해주어서 최단경로의 값을 갖고 있게 한다.

총평

BFS에 익숙해지기 위해 좋은 기초 문제이다.