난이도는 골드3, 핵심 구현 포인트는 그래프 내부 사이클 요소의 갯수를 구하는 것이다.
일반적으로 dfs 나 bfs 를 사용해서 그래프 탐색을 하는 경우에는 Visit 배열을 사용하였지만, 사이클 요소를 판별하기 위해서 Check 라는 2차원 배열 요소를 추가하였다.
이 구현법을 잘 숙지한다면, 그래프 내부 사이클 갯수와 사이클 요소의 수를 구하는데 용이할 것 같다.
void dfs(int start) {
int next = map[start];
if (visit[next] == 0) {
visit[next] = 1;
dfs(next);
}
else if (check[next] == 0) { // 이미 방문은 하였으나, 사이클 여부 확인이 안된 경우
for (int i = next; i != start; i = map[i]) {
member++; // 본인 제외 사이클 멤버 수 카운트
}
member++; // 본인 카운트
}
check[start] = 1;
}핵심 로직
오답 노트
사이클 로직 구현을 생각하지 못하고 1인 팀을 먼저 소거한 후, 일반적인 DFS로 팀 멤버를 구하려고했다. 하지만 일반적인 DFS 알고리즘을 사용할 경우, 미완성된 사이클 내부에 존재하는 완성사이클을 판별하지 못했다. 예를 들어,
1 -> 2
2 -> 3
3 -> 4
4 -> 2
의 간선 정보를 가진 그래프가 있다. 이 경우 기존의 DFS(1) 로 탐색을 시작한다면 사이클의 존재를 분간할 수 없다. 시작점은 1인데, 종착점은 2 이기 때문이다. 그리고 이미 Visit 배열에 방문 처리를 하였기에 1, 2, 3, 4 번 노드는 다음 방문 대상에서 제외되고 탐색은 종료된다.
사실 위의 경우 2, 3, 4 요소만을 따져보았을 때 사이클이 만들어지고, 위의 로직은 실패로직이다.
따라서 Chech 배열을 추가하여, 단순 방문 여부 + 방문 완료(사이클 여부까지 확인) 까지 확인할 수 있는 추가 요소를 도입한다. 새롭게 구현한 DFS 함수로 위의 간선정보를 가진 그래프를 다시 탐색해보자.
마지막 요소는 2번 노드다. 마지막 노드인 이유는, 방문 불가능한 노드이기 때문이다.
하지만 아직 DFS 방문 도중이기 때문에 check[2] = 1 상태는 아닌것이다. 따라서 for 문의 사이클 판별 로직으로 들어간다.
int i = next 로 i는 가장 처음 마지막 노드 로 초기화된다. 그리고 매 반복마다 map[i] 로 초기화된다. 마지막 노드 -> 마지막 노드의 직전노드 까지 사이클 요소의 갯수를 세는 것이다. 예를들어 3 -> 3 의 노드 1개로 만들어진 사이클이 있다면, 마지막 노드 = 3, 마지막 직전의 노드 = 3 이므로 1인팀 역시 판별이 가능하다.
한 번은 틀릴 수 있지만, 기억해서 다음부터는 구현할 수 있도록 하자.
전체코드는 다음과 같다.
#include<iostream>
#include<vector>
using namespace std;
int T, N;
int map[100001];
int visit[100001];
int check[100001];
int member = 0;
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> map[i];
}
}
void clear() {
member = 0;
memset(map, 0, sizeof(map));
memset(visit, 0, sizeof(visit));
memset(check, 0, sizeof(check));
}
void dfs(int start) {
int next = map[start];
if (visit[next] == 0) {
visit[next] = 1;
dfs(next);
}
else if (check[next] == 0) { // 이미 방문은 하였으나, 사이클 여부 확인이 안된 경우
for (int i = next; i != start; i = map[i]) {
member++; // 본인 제외 사이클 멤버 수 카운트
}
member++; // 본인 카운트
}
check[start] = 1;
}
int main() {
cin >> T;
while (T > 0) {
input();
for (int i = 1; i <= N; i++) {
if (visit[i] == 0) {
visit[i] = 1;
dfs(i);
}
}
cout << N - member << '\n';
clear();
T--;
}
return 0;
}
