[Python] 너비 우선 탐색(BFS)

너비 우선 탐색(Breadth First Search)

• BFS의 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것이다.

• while queue를 이용한다.

• 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식

• DFS와 마찬가지로 check 배열을 만들어 큐에 넣을 때 방문했다고 체크해야 한다.

• 최단거리(가중치가 1일 때), 최솟값을 찾는 문제에서 많이 사용한다.

BFS의 조건

BFS를 이용해 해결할 수 있는 문제는 아래와 같은 조건을 만족해야 한다.

1. 최소 비용 문제

2. 간선의 가중치가 1

3. 정점과 간선의 개수가 적어야 한다.(적다는 것은 문제의 조건에 맞춰서 해결할 수 있다는 것을 의미)

4. 간선의 가중치가 문제에서 구하라고 하는 최소 비용과 의미가 일치해야 한다.
   즉, 거리의 최소값을 구하는 문제라면 구하는 가중치는 거리를 의미하고, 시간의 최소값을 구하는 문제라면 가중치는 시간을 의미해야 한다.
   
    
   

가중치가 모두 1이 아닐 때 주의해야 한다.

• 예를 들어 현재 a지점에서 a+1로 움직일 때는 비용이 안들지만
a+2로 이동할 때는 비용이 1이 든다고 하면 이런 경우에는 가중치가 0와 1로 다르다.
이럴 때는 가중치가 0인 것은 큐의 앞자리(appendleft())로 해결하고
가중치가 있는 것은 큐의 뒷자리(append())로 해결하자.

현재 정점 : 1
순서 : 1
큐 : 1



현재 정점 : 1
순서 : 1 2 5
큐 : 1 2 5



현재 정점 : 2
순서 : 1 2 5
큐 : 2 5



현재 정점 : 2
순서 : 1 2 5 3
큐 : 2 5 3



현재 정점 : 5
순서 : 1 2 5 3
큐 : 5 3



현재 정점 : 5
순서 : 1 2 5 3 4
큐 : 5 3 4



현재 정점 : 3
순서 : 1 2 5 3 4
큐 : 3 4



현재 정점 : 4
순서 : 1 2 5 3 4
큐 : 4



현재 정점 : 4
순서 : 1 2 5 3 4 6
큐 : 4 6



현재 정점 : 6
순서 : 1 2 5 3 4 6
큐 : 6



• 큐가 비어있으므로 탐색 종료
현재 정점 : 6
순서 : 1 2 5 3 4 6
큐 :

from collections import deque
n,m=map(int,input().split())
map_=[list(map(int,input())) for _ in range(n)]
dist=[[-1 for _ in range(m)] for _ in range(n)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]


sx,sy,ex,ey=0,0,n-1,m-1
cnt=0
def bfs():
    q=deque()
    q.append((sx,sy))
    dist[sx][sy]=1
    while q:
       
        x,y=q.popleft()
        for k in range(4):
            nx,ny=x+dx[k],y+dy[k]
            if 0<=nx<n and 0<=ny<m:
                if dist[nx][ny]==-1 and map_[nx][ny]==1:
                    dist[nx][ny]=dist[x][y]+1
                    q.append((nx,ny))
                    
bfs()
print(dist)

bfs 최소값으로 목적지 도달 기본 코드