백준 # 벽을 부쉈는지, 부수지 않았는지에 대한 방문기록이 나뉜다 import sys from collections import deque input = sys.stdin.readline n,m = map(int, input().split()) graph = [input() for _ in range(n)] visited = [[[0]*2 for _ in range(m)] for _ in range(n)] # 3차원 배열 dx, dy = (1,-1,0,0), (0,0,1,-1) # 이동 경로 def bfs(): queue = deque([(0,0,0)]) visited[0][0][0] = 1 # 출발장소 방문체크 while queue: popx, popy, bukbbu = queue.popleft() i..
너비우선탐색
BFS (너비우선탐색) 시작노드에서 시작한 뒤 다음 깊이로 진행하기 전 출발점에서 발생한 모든 분기를 탐색한 후, 다음 레벨로 진입한다. 갈림길의 모든 지점들을 탐색한 뒤 갈림길에서 발생한 모든 갈림길을 다시 순차적으로 탐색하는 모습이 가로로 훑는 모양새이다. DFS의 경우 무한루프나 스택오버플로의 우려가 있었지만, BFS의 경우 모든 경로에 대해 동시에 탐색을 진행하므로 그럴 걱정은 없다. BFS의 특성 1. BFS는 재귀로 구현할 수 없다. 2. 가중치가 없는 그래프에서 두 노드 사이의 최단경로나 임의의 경로를 구하는 데 사용한다. 3. DFS보다 검색에서 유리하다. (DFS는 조건을 만족하는 순회에 초점) 4. 방문한 노드들을 저장한 후 차례대로 꺼내는 FIFO (선입선출) 방식으로 탐색을 진행하기..
