방향 그래프가 주어졌을 때 종종 이 그래프 내에서 \(Cycle\)의 존재 유무를 확인해야 할 때가 있다. 이 글에서는 방향 그래프 내에서 싸이클의 존재 유무를 알아내는 알고리즘을 소개하려 한다.기본적인 알고리즘\(Cycle\)의 정의를 한번 생각해 보자. \(Cycle\)이란 정점 \(u\)에서 시작해 어떠한 경로를 지나 다시 \(u\)로 돌아오는 경로가 있다면 이를 \(Cycle\)이라고 한다. 그리고 그래프 내에 이러한 \(Cycle\)이 한개라도 있다면 \(Cycle\)이 존재하는 그래프가 된다. 그렇다면 특정한 시작 정점 \(u\)를 잡고 \(dfs\)를 실행해 다시 시작정점 \(u\)로 돌아오는 경로가 있는지 확인하는 알고리즘을 만든 뒤 모든 정점에 대해 해당 알고리즘을 실행하면 \(Cycle..
graph
여기를 클릭해 주세요. 문제 링크 https://www.acmicpc.net/problem/3136 문제 요약 문제에서 주어진 방향대로 선을 그어나갔을 때 생기는 평면의 개수를 출력하는 문제. 문제 풀이 이 문제를 처음 본다면 당황할 수 있다. 언제 공간이 생기는지 아는것도 힘들 뿐더러 그걸 알았다고 하더라도 공간을 어떻게 세어야 할지 막막하기 때문이다. 하지만 정수 좌표를 버텍스라고 생각하고, 선들을 엣지라고 생각한다면 그래프에서의 평면의 개수를 찾는 문제로 치환이 된다. 일반적으로 그래프에서 평면의 개수를 찾는것은 어렵지만 선을 그어서 생기는 그래프는 평면그래프 라는것을 깨닫는 순간 문제는 매우 쉬워진다. 평면그래프에는 아래와 같은 공식이 있다. \(V\ -\ E\ +\ F\ =\ 2\) \(V\)은..
여기를 클릭해 주세요. 문제 링크 https://www.acmicpc.net/problem/6135 문제 요약 \(N\)개의 정점으로 이루어진 가중치가 있는 방향 그래프가 주어 진다. 그 뒤 \(Q\)개의 쿼리가 주어지는데 각각의 쿼리마다 두 개의 수 \(u\), \(v\)가 주어진다. 각 쿼리에 대해서 구해야 하는 값은 아래와 같다. \(u\), \(v\)로 가는 경로를 하나 선택했을 때 그 경로에 있는 엣지들의 무게들 중 가장 무거운 값이 있다고 하자. 이 값을 최소화 시키는 경로를 하나 찾는게 문제다. 실제 경로는 찾을 필요가 없고 최대중에 최소의 값만 찾으면 되기 때문에 쉽게 해결할 수 있다. 문제 풀이 \(D[u][v]\) = \(u\)에서 \(v\)로 가는 경로 중 만나는 엣지의 무게의 최대의..
