Devlog_by_0giru

이전에 포스팅 했던 깊이우선 탐색(DFS)와 또 다르게 널리 이용되는 탐색 이론이다. DFS가 이름 처럼 하나의 노드에서 도달 가능한 깊은 노드까지 먼저 탐색한다면, 넓이우선 탐색 BFS는 하나의 노드로부터 주변의 모든 노드로 뻗어나가며 탐색하는 방법이다. 넓이 우선 탐색은 큐 자료구조를 이용한다. 큐의 선입선출 특성을 이용하는데, 큐의 가장 첫 번째 노드와 연결된 노드를 큐에 집어넣고, 첫 번째 노드를 큐에서 빼낸 후 방문처리를 하는 것을 반복한다. 아래와 같은 그래프가 있고 1번 노드로부터 BFS를 이용해 탐색을 시작한다고 하자. +) 탐색을 시작하는 노드는 어디로 해도 상관없지만 숫자가 작은 노드부터 오름차순으로 하는 것이 편하고 또 그것을 관례적으로 따르기도 한다. 시작 노드인 1번 노드를 큐에 ..

# 테스트 케이스 2 통과 / 실패 def solution(tickets): nation_num = len(tickets) graph = [] graph_new = [] result = [] for inf in tickets: graph.append([inf[0]]) for inf in tickets: for i in range(nation_num): if inf[0] == graph[i][0]: graph[i].append(inf[1]) for inf in graph: if inf not in graph_new: graph_new.append(inf) for inf_new in graph_new: temp1 = inf_new[0] inf_new.sort() temp2 = inf_new.index(tem..

# 바이러스 from collections import deque # N은 노드의 개수 # M은 노드가 연결된 정보의 입력 횟수 N = int(input()) M = int(input()) # BFS알고리즘 활용을 위해 collections 모듈의 deque를 활용 queue = deque() result = [] # 0번 인덱스는 활용하지 않고, 방문 여부를 체크해 줄 리스트 생성. 초기에는 모두 False이다. visited = [False] * (N+1) # 전체 그래프를 표현하기 위한 빈 리스트 생성 graph = [[] for _ in range(N+1)] # 입력 정보를 이용해 그래프 생성을 위한 for 루프 for _ in range(M): i, j = map(int, input().spli..

from collections import deque # dfs 함수 def dfs(par_graph, par_v, par_visited): visited[par_v] = True result_dfs.append(par_v) for i in par_graph[par_v]: if not visited[i]: dfs(par_graph, i, par_visited) #bfs 함수 def bfs(par_graph, par_v, par_visited): visited[par_v] = True queue.append(par_v) while queue: v = queue.popleft() result_bfs.append(v) for i in par_graph[v]: if not visited[i]: queue.app..