[G3] 백준 9466번 텀 프로젝트 C++ 깊이 우선 탐색

리뷰

 

https://www.acmicpc.net/problem/9466

싸이클에 속하지 못한 노드의 개수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• t : 테스트 케이스의 개수를 저장할 변수
• n : 노드의 개수를 저장할 변수
• cnt : 싸이클에 속하지 못한 노드의 개수를 저장할 변수
• lst : 이동할 다음 노드를 저장할 배열
• v : 방문 상태를 저장할 배열
• cycle : 싸이클에 속했는지 여부를 저장할 배열

 

함수

1. dfs

void dfs(int node)

 

깊이 우선 탐색을 통해 싸이클 유무를 찾기 위한 함수

1. 매개 변수로 탐색할 현재 노드의 번호를 전달 받는다.
2. v배열에 현재 노드의 상태를 1로 변경해 준다.
3. 다음 노드를 변수 next에 저장해 준다.
4. v배열의 next값이 0이라면 dfs함수에 next를 전달하여 재귀를 수행한다.
5. v배열의 next값이 1이라면 cycle배열의 next에 true를 저장해 준다.
6. 변수 cur에 next값을 복사해 주고 cur과 node가 같아질 때 까지 while 루프를 수행해 준다.
7. cur을 cur의 다음 노드값으로 저장해 준 뒤 cycle배열의 cur에 true를 저장해 준다.
8. 루프에서 빠져나온 뒤 cycle배열의 node에 true를 저장해 준다.
9. 위 과정을 마친 후 v배열에 현재 노드의 상태를 2로 변경해 준다.

 

문제풀이

1. t값을 입력 받고, t번의 while 루프를 수행하여 테스트 케이스를 실행해 준다.
2. 매 테스트 케이스 마다 n값을 입력 받고, lst배열에 n개의 노드의 다음 노드 선택 정보를 입력 받는다.
3. memset 메서드를 통해 이미 사용했던 v, cycle배열의 값을 초기화 해준다.
4. 1번부터 n번 노드까지 v배열의 값이 0이라면 각 노드의 번호를 dfs함수의 매개변수로 전달하여 재귀를 수행한다.
5. 변수 cnt를 0으로 초기화 하고, 1 ~ n번 노드 중 cycle의 값이 false인 경우 cnt를 증가시켜 준다.
6. cnt에 저장된 값을 출력하고 줄 바꿈을 수행해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 싸이클의 개수뿐만 아니라 싸이클에 속한 노드의 수를 구해야 하기 때문에 싸이클 발견 시 while 루프를 통해 해당 싸이클에 속한 노드를 다시 한 번 방문해 주었다.

 

정답 코드

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int N = 100001;
int t, n, cnt;
int lst[N];
int v[N];
bool cycle[N];

void dfs(int node) {
	v[node] = 1;

	int next = lst[node];
	if (v[next] == 0) dfs(next);
	else if (v[next] == 1) {
		cycle[next] = true;

		int cur = next;
		while (cur != node) {
			cur = lst[cur];
			cycle[cur] = true;
		}
		cycle[node] = true;
	}
	v[node] = 2;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; ++i) cin >> lst[i];

		memset(v, 0, sizeof(v));
		memset(cycle, 0, sizeof(cycle));
		for (int i = 1; i <= n; ++i) {
			if (!v[i]) dfs(i);
		}

		cnt = 0;
		for (int i = 1; i <= n; ++i) {
			if (!cycle[i]) cnt++;
		}
		cout << cnt << "\n";
	}
}