#5 탐색 알고리즘 BFS

• BFS(Breadth First Search) 알고리즘 : 너비 우선 탐색
  가까운 노드부터 탐색하는 알고리즘
  <-> 최대한 멀리 있는 노드를 우선으로 탐색하는 DFS와 반대

BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석
인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

① 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
② 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

bfs 예제)

from collections import deque

def bfs(graph, start, visit) :
    queue = deque([start])
    visit[start] = True
    while queue :
        v = queue.popleft()
        print(v, end= " ")
        for i in graph[v] :
            if not visit[i] :
                queue.append(i)
                visit[i] = True
                
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
    ]
    
visit = [False] * 9

bfs(graph, 1, visit)
# 1 2 3 8 7 4 5 6

bfs 함수는 처음에 시작할 때만 한 번 사용하고 bfs 함수 내 while문이 계속 돌아가면서 진행된다.

#4의 DFS 함수와 BFS 함수 이용하여 백준 1260 해결

이코테 Chap5. 실전문제4) 미로탈출, 백준 2178

from collections import deque 
import sys

n, m = map(int, input().split())

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

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

def bfs(x, y) :
    queue = deque()
    queue.append((x, y))
    while queue :
        x, y = queue.popleft()
        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] + 1
                queue.append((nx, ny))
    return graph[n-1][m-1]

print(bfs(0,0))

풀면서 막힌 부분은

for _ in range(n) :
    graph.append(list(map(int, input())))

이 부분이다. 속도를 빠르게 하기 위해 sys.stdin.readline을 쓰면
invalid literal for int() with base 10: '\n'
라는 에러가 뜬다 ㅜㅜ
처음에는 도댜ㅐ체 뭐가 잘못인가 해서 30분동안 구글링을 했는데
알고보니 sys.stdin.readline 를 쓰면 입력 뒤에 \n 이 붙는다고 한다.. ㅜㅅㅜ

graph.append(list(map(int,input().rstrip())))
이렇게 뒤에 rstrip() 라는 공백제거함수를 사용해야한다. 기억하자!
(*rstrip : 문자열에 오른쪽 공백이나 인자가된 문자열의 모든 조합을 제거)