그래프에서 사이클을 이루지 않는 정점을 구하는 문제. 모든 정점에 대해서 순회 알고리즘(DFS, BFS)을 통해 자기 자신까지 되돌아올때까지 탐색하면 으로 풀 수 있다. 하지만 입력이 이라서 이 풀이는 불가능하다. 이 문제를 많이 고민 했고, 블로그 풀이도 여럿 찾아보았지만 풀이가 이해는 되는데 직관적으로 와닿지는 않아서 푸는데 오래걸렸다. 이 글에서는 내가 생각한 대로 최대한 직관적으로 풀이하고자 한다.
어떤 학생이 프로젝트를 함께 하고 싶은 학생을 선택하면 학생 사이에 선택자와 피선택자 관계가 생기는데, 우리는 이를 방향 그래프의 간선으로 생각할 수 있다. 그래프에서 사이클의 정의는 중복되지 않는 간선의 순열인데, 그 중에서 시작점과 끝점이 같은 경우를 말한다. 문제에서 주어지는 한 팀이 될 수 있는 조건은 사이클의 정의와 일치한다. 우리는 이 중에서 사이클에 속하지 않는 정점의 개수를 구하고 싶은데, 이를 구하는 것보다는 반대로 사이클에 속하는 정점 수 을 구한 후에 을 하는 것이 더 쉽다. 모든 정점은 사이클에 포함되거나 포함되지 않기 때문이다.
가장 처음에 설명한 것 처럼, 의 풀이로는 문제의 조건에 맞춰 정답을 찾을 수 없다. 그런데 모든 정점에 대해 사이클을 찾는 알고리즘이 의 시간 복잡도를 가지는 이유는 정점들이 중복 방문 가능하기 때문인데, DFS나 BFS를 이용하면 에 가능하므로 이를 이용해보자. 이 풀이에서는 각 정점마다 간선이 하나 뿐이므로 구현이 간단한 DFS를 이용한다.
그래프가 연결 그래프라는 보장이 없으므로 모든 정점에 대해서 DFS 함수를 한번씩 호출 해줘야하는데, 우리는 이 과정에서 두가지를 알 수 있다.
1) 방문한 정점이 현재 호출한 DFS함수가 방문했던 정점이라면
그 정점에서 간선을 타고 가면 무조건 자기 자신으로 돌아오게 되고, 그 경로의 길이가 사이클의 크기가 된다.
2) 이전에 호출한 DFS함수가 방문한 지점은 방문할 필요가 없다.
정점 하나에서 시작하는 간선은 하나 뿐인데, 이 간선을 따라가면서 만나는 정점들은 사이클 여부를 이미 확인했기 때문이다.
막상 설명하려고 보니 너무 두서가 없어진 것 같다.
public class Main {
static int[] adj;
static boolean[] currentVisit; // 현재 진행되고 있는 DFS함수가 방문했는지 여부
static boolean[] visit; // 이전의 DFS호출에서 정점을 방문했는지 여부
static int cycle; // 사이클을 이루는 노드의 개수
static void dfs(int here) {
currentVisit[here] = true;
int there = adj[here];
// 이전의 DFS의 호출에서 방문하지 않은 인접 정점을 방문한다
// 이전에 방문한 정점들은 사이클에 포함되거나 포함되지 않기 때문에 확인해줄 필요가 없다
if (!visit[there]) {
if (!currentVisit[there]) {
dfs(there);
} else {
cycle++;
// 사이클을 이루는 간선의 개수를 센다(간선의 개수가 노드의 개수)
for (int i = there; i != here; i = adj[i]) cycle++;
}
}
visit[here] = true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
for (int tc = 0; tc < TC; tc++) {
int N = Integer.parseInt(br.readLine());
adj = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= N; i++) adj[i] = Integer.parseInt(st.nextToken());
currentVisit = new boolean[N + 1];
visit = new boolean[N + 1];
cycle = 0;
for (int here = 1; here <= N; here++)
if (!visit[here]) dfs(here);
System.out.println(N - cycle);
}
}
}
그렇다면 이 풀이의 시간 복잡도는 어떻게 될까? 기존의 DFS에서 약간 변형하긴 했지만, dfs(there)는 해당 정점이 방문하지 않은 정점일 때만 호출되므로 정점을 두번 방문하지 않게 된다.
그렇기 때문에 로 일반적인 DFS와 같게되는데 문제는 사이클의 크기를 계산하는 부분이다. 하지만 이 또한 사이클을 구성하는 원소를 중복으로 세지 않으므로 반복 횟수는 최대 O(|N|)임을 알 수있고 최종 시간 복잡도는 이 된다.