2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ** 문제 유형 DFS, BFS ** 풀이 단순히 시작 정점에서부터 도달할 수 있는 노드의 수를 계산하는 문제 DFS or BFS를 이용하여 방문하게 되는 노드의 개수를 계산 컴퓨터의 수가 적으므로, DFS를 이용해 빠르게 문제를 푸는 것이 유리 def dfs(now_pos): global count visited[now_pos] = True for next_pos in adj[now_pos]: if not visited[next_pos]: count += 1 dfs..

1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net ** 문제 유형 이진 탐색 ** 풀이 다리의 개수 M은 최대 100,000이며, 중량 제한 C는 최대 1,000,000,000 이진 탐색을 이용하여 O(M * logC)에 문제 해결 100,000 * 30 = 3,000,000 한번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 이진 탐색으로 찾음 반복적으로 중량을 설정하여, 이동이 가능한 경로를 찾음 최대 중량과 최소 중량 설정 중간값은 초기화할 때 최소 중량..

** DFS 알고리즘 구현 자료구조 스택과 큐를 활용함 need_visit 스택과 visited 큐, 두 개의 자료 구조를 생성 BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS 는 스택과 큐를 활용한다는 차이가 있음을 인지해야 함 큐와 스택 구현은 별도 라이브러리를 활용할 수도 있지만, 간단히 파이썬 리스트를 활용할 수도 있음 def dfs(graph, start_node): visited, need_visit = list(), list() need_visit.append(start_node) while need_visit: node = need_visit.pop() # BFS와 차이: 스택 정책 if node not in visited: visited.append(node) need_visit..

** 그래프(Graph) 실제 세계의 현상이나 사물을 노드와 간선으로 표현 ** 그래프 관련 용어 노드 (Node): 위치 (= 정점, Vertex) 간선 (Edgd): 위치 간의 관계를 표시한 선, 노드를 연결한 선 (= Link, Branch) 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 노드 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length): 경로를 구성하기 위해 사용된 간선의 수 단순 경로 (Simple Path): 처음 정점과 끝 정점을 제외하고 중복..