BFS

코드 # 가중치 없는 최단거리 -> bfs import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dx, dy = (1,-1,0,0), (0,0,1,-1) # 상하좌우 이동 graph = [[*map(int, input().split())] for _ in range(n)] visited = [[0]*m for _ in range(n)] # 방문기록 def bfs(i,j): queue = deque([(i,j)]) while queue: px,py = queue.popleft() for i in range(4): nx = px + dx[i] ny = py + dy[i] if 0

코드1 # BFS로 해결 import sys from collections import deque input = lambda: sys.stdin.readline().rstrip() # 람다함수로 사용 tc = int(input()) def bfs(s,g,v,t): queue = deque([s]) v[s] = t[s] endpoint = [] # 끝에 도달한 값을 모아줄 리스트 while queue: popnum = queue.popleft() if g[popnum]: # 올라갈 값이 있는 경우 for i in g[popnum]: if v[i] < v[popnum]+t[i]: # 큰값으로 초기화 v[i] = v[popnum]+t[i] queue.append(i) else: endpoint.append(p..

백준 # 벽을 부쉈는지, 부수지 않았는지에 대한 방문기록이 나뉜다 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..

코드 # 처음 시작, 마지막 점 도착 => 한 점에서 다른 한 점으로의 최단거리 # 가중치는 0~9사이의 정수이므로 다익스트라 알고리즘 사용 가능 # 상하좌우 움직이는 경우를 파악해야 하므로 bfs 풀이 아이디어를 빌려온다. from heapq import heappop, heappush import sys INF = 987654321 input = sys.stdin.readline def dijkstra(first,x,y): dx,dy = [1,-1,0,0], [0,0,1,-1] # 상하좌우 움직일 경우의 수 queue = [(first, x,y)] # 비용, 행, 열 visited[x][y] = first while queue: now, popx,popy = heappop(queue) if now >..

코드 1 (BFS 이용) import sys from collections import deque input = sys.stdin.readline n,m,k,x = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [0]*(n+1) # 방문 기록용 for _ in range(m): s,e = map(int,input().split()) graph[s].append(e) # 단방향 그래프 def bfs(start): queue = deque([start]) visited[start] = 1 while queue: num = queue.popleft() for i in graph[num]: if not visited[i]: visite..

코드 from collections import deque subin, dongsang = map(int, input().split()) path = [0]*100001 # 이전에 방문했던 노드를 기록할 리스트 visited = [0]*100001 # 몇 번째로 해당 노드를 방문했는지 기록할 리스트 def bfs(start): # 가중치가 없고, 최단거리를 찾아야하므로 bfs 이용 queue = deque([start]) visited[start] = 1 # 출발 전 방문기록 while queue: popnum = queue.popleft() if popnum == dongsang: return visited[popnum]-1 # 만약 pop한 값이 동생이 있는 곳과 같다면 함수 종료 for i in [..

BFS (너비우선탐색) 시작노드에서 시작한 뒤 다음 깊이로 진행하기 전 출발점에서 발생한 모든 분기를 탐색한 후, 다음 레벨로 진입한다. 갈림길의 모든 지점들을 탐색한 뒤 갈림길에서 발생한 모든 갈림길을 다시 순차적으로 탐색하는 모습이 가로로 훑는 모양새이다. DFS의 경우 무한루프나 스택오버플로의 우려가 있었지만, BFS의 경우 모든 경로에 대해 동시에 탐색을 진행하므로 그럴 걱정은 없다. BFS의 특성 1. BFS는 재귀로 구현할 수 없다. 2. 가중치가 없는 그래프에서 두 노드 사이의 최단경로나 임의의 경로를 구하는 데 사용한다. 3. DFS보다 검색에서 유리하다. (DFS는 조건을 만족하는 순회에 초점) 4. 방문한 노드들을 저장한 후 차례대로 꺼내는 FIFO (선입선출) 방식으로 탐색을 진행하기..