#그래프 9

• PS 2024-05-23

  [간만에 스터디] LeetCode Number of Provinces

  Number of Provinces 코드 접근 및 풀이방법 1. 그래프탐색(BFS or DFS)은 그래프에 존재하는 모든 간선을 통해 결국 모든 노드를 방문한다. 1. 단 이 문제의 경우 그래프가 양방향 간선이 존재하기 때문에 반드시

• PS 2021-07-15

  코드포스 938D Buy a Ticket

  문제 도시가 N개 있고, 양방향 기찻길이 M개 있다( i 번째 길은 u ↔ v 를 비용 w 로 잇는다). 각 도시 i 에는 콘서트 티켓 값 a i 가 있다. 각 도시 i 마다 , 어떤 도시 j 로 가서(머물러도 됨) 콘서트를 보고 다

• PS 2021-07-13

  백준 11375 열혈강호

  문제 회사에 직원이 N명, 해야 할 일이 M개 있다. 각 직원은 자신이 할 수 있는 일들 중 하나만 담당할 수 있고, 각 일도 한 명 만 담당한다. 할 수 있는 일의 최대 개수를 구하면 된다. - 입력 : 1번째 줄에 N M . 이어

• PS 2021-07-01

  백준 16118 달빛여우

  문제 그루터기 N개가 오솔길 M개로 이어져 있다(각 길의 길이 d ). 여우 는 1번 그루터기에서 출발해 모든 길을 같은 속도로 달린다. 늑대 도 1번에서 출발하지만, 오솔길을 지날 때마다 빠르게(2배속) ↔ 느리게(0.5배속) 를

• PS 2019-05-12

  최소 신장 트리 (MST) 정리

  최소 신장 트리 (MST) 연결된 가중치 그래프에서, 모든 정점을 잇되 사이클 없이(즉 트리로) 연결하는 부분 그래프 중에서 간선 가중치의 합이 최소 인 것. 정점이 V개면 간선은 정확히 V-1개를 쓴다. "모든 도시를 최소 비용으로

• PS 2019-03-10

  위상 정렬 (Topological Sort) 정리

  위상 정렬 방향 그래프에서 선후 관계(A 다음에 B)를 어기지 않도록 정점들을 한 줄로 나열하는 것. "선수 과목을 다 들어야 다음 과목을 듣는다", "이 작업이 끝나야 저 작업을 시작한다" 같은 순서 제약을 만족하는 순서를 구할 때

• PS 2018-07-08

  다익스트라 (Dijkstra) 정리

  다익스트라 어떤 그래프 G와 시작 정점 st가 주어질 때, st로부터 다른 모든 정점으로의 최단 경로 길이를 구하는 알고리즘. 이러한 특징으로 시작점 고정 최단거리 알고리즘 이라고도 한다. 다익스트라 알고리즘은 매 단계마다 도달할 수

• PS 2018-05-13

  너비 우선 탐색 (BFS) 정리

  BFS (너비 우선 탐색) 시작 정점에서 가까운 정점부터 차례대로, 레벨 단위로 퍼져 나가며 탐색하는 방법. 큐(Queue)를 사용한다. DFS가 한 갈래를 끝까지 파고드는 것과 반대로, BFS는 시작점에서 거리 1인 정점들을 모두

• PS 2018-05-06

  깊이 우선 탐색 (DFS) 정리

  DFS (깊이 우선 탐색) 그래프나 트리에서 한 정점을 시작으로, 갈 수 있는 곳까지 최대한 깊이 들어갔다가 더 갈 곳이 없으면 직전 갈림길로 되돌아와 다른 길을 탐색하는 방법. 되돌아오는(backtrack) 동작이 핵심이라, 재귀