BFS (Breadth First Search, 너비 우선 탐색)
BFS (Breadth First Search, 너비 우선 탐색) 시작 정점으로부터 거리가 가까운 정점 순(너비 우선)으로 인접한 노드를 탐색하는 알고리즘 특징 - 최단 경로를 찾을 때 사용 - 일반적으로 큐(Queue) 사용 (선입선출 방식을 사용해야 함) - 재귀적 x - 시간복잡도 : 인접 리스트로 구현된 경우 O(|V|+|E|), 인접 행렬로 구현했을 경우 O(|V|^2) - 입력 : 노드의 갯수 n, 그래프 graph, 시작 노드 v 장점 - 최단 경로를 보장 - 단순 검색 속도가 DFS보다 빠르다. 단점 - 경로가 긴 경우 많은 메모리를 필요로 한다. Python 구현 코드 n = 6 graph = {1: [3, 2], 2: [3, 1, 4, 5], 3: [6, 4, 2, 1], 4: [3, ..
https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr from collections import deque def solution(n, edge): answer = 0 graph = {i:[] for i in range(1, n+1)} for i, j in edge: graph[i].append(j) graph[j].append(i) visited = [0] * (n+1) visited[1] = 1 queue = deque([[1, 0]]) while(queue): node, dept..