코드 # 가중치가 0, 1만 존재하고 최단거리를 찾는 문제 # 0-1 bfs을 이용하면 쉽게 해결할 수 있다. import sys from collections import deque input = sys.stdin.readline n = int(input()) graph = [list(input().rstrip()) for _ in range(n)] visited = [[0]*n for _ in range(n)] # 방문기록 리스트 dx, dy = [1,-1,0,0], [0,0,1,-1] # 이동할 수 있는 경우의 수 def bfs(start,end): queue = deque([(start,end)]) visited[start][end] = 1 # 처음 시작점 방문 기록 while queue: x,y..
0-1bfs
코드 1 (0-1 BFS 풀이) from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [input() for _ in range(m)] visited = [[0]*n for _ in range(m)] def bfs(): # 가중치가 0 또는 1만 있기 때문에, 0-1 bfs가 떠올랐다. queue = deque([(0,0)]) dx, dy = [1,-1,0,0],[0,0,1,-1] # 이동할 수 있는 경우의 수 visited[0][0] = 1 # 첫번째 노드 방문기록을 해준다 while queue: popx, popy = queue.popleft() if popx ..
0-1 BFS 0-1 bfs는 가중치가 0과 1만 있는 최단 경로 문제를 말한다. 시간복잡도는 O(V+E) (V는 노드, E는 간선)으로, 조건을 만족하는 경우 다익스트라 알고리즘보다 더 효율적으로 작동한다. 일반적인 BFS 탐색과 동일하지만, 가중치가 0인 정점이 존재하기 때문에 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 한다. 즉, 결과 값이 방문 횟수의 최소가 아닌 가중치가 최소인 경우를 찾기 때문에 가중치가 낮은 경로부터 탐색해야 한다. 0-1 BFS 동작 1. 덱의 front에서 현재 노드를 꺼낸다. 2. 연결된 인접 노드를 살펴본다. 3. 현재까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 소비된 비용을 갱신해준다. 4. 노드..
