위상 정렬이란?위상 정렬은 방향 그래프(DAG, Directed Acyclic Graph)에서 노드들을 순서대로 정렬하는 알고리즘이때 정렬된 순서는 모든 간선 (A → B)에 대해 A가 B보다 먼저 나와야 하는 순서를 보장 주로 다음과 같은 문제 상황에서 사용:작업 순서 정하기 (예: 건물을 짓기 전에 먼저 지어야 하는 건물 존재)강의 수강 순서 (선수 과목이 있는 경우)프로젝트 모듈 간의 의존성 처리 동작 방식 (Kahn's Algorithm - BFS 기반)모든 노드의 진입 차수(indegree)를 계산한다.진입 차수가 0인 노드들을 큐에 넣는다.큐에서 하나씩 꺼내어 결과 리스트에 추가하고 연결된 노드의 진입 차수를 1 감소시킨다.새로 진입 차수가 0이 된 노드를 큐에 넣는다.큐가 빌 때까지 반복한..

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 (Depth-First Search) 깊이 우선 탐색DFS는 그래프 탐색 알고리즘 중 하나로시작 노드에서 가능한 깊이까지 먼저 탐색한 뒤더 이상 깊게 갈 곳이 없을 경우 되돌아가며(Backtracking) 탐색을 이어가는 방식입니다. DFS 특징방문 경로를 깊이 우선으로 추적재귀 호출 또는 스택(Stack)을 활용해 구현 가능그래프의 연결 요소 탐색에 유용순환 구조(사이클)나 미로 찾기 문제 등에 자주 사용됨 DFS vs BFS구분DFSBFS자료구조스택(Stack) or 재귀큐(Queue)방문 순서깊이 우선 → 다음 분기로 이동너비 우선 → 레벨 순서대로 이동구현 방식주로 재귀 또는 수동 스택큐로 구현사용 예시백트래킹, 미로, 트리 탐색 등최단 거리, 레벨 기반 탐색 등 DFS 알고리즘 구현DFS..

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