[백준 9466번 C/C++] 텀 프로젝트

 

[백준 9466번 C/C++] 텀 프로젝트

 

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

9466번: 텀 프로젝트

---

 

해결전략

 

깊이우선탐색 DFS

 

---

 

정답코드

 

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

int T; // 테스트 케이스의 수
int n; // 노드의 수
vector<int> v; 		  // 각 노드에서 다른 노드로의 링크를 저장하는 벡터
vector<bool> visited; // 각 노드의 방문 여부를 저장하는 벡터
vector<int> done; 	  // 각 노드가 처리되었는지 여부를 저장하는 벡터
int cnt; // 사이클에 포함된 노드의 수를 저장하는 변수

void DFS(int start)
{
	visited[start] = true; // 시작 노드를 방문했다고 표시
	int next = v[start]; // 다음에 방문할 노드

	if (visited[next] == false) { // 다음 노드가 아직 방문되지 않았다면
		DFS(next); // 다음 노드로 DFS를 재귀적으로 호출
	}
	else {
    	// 다음 노드가 아직 처리되지 않았다면(이전에 방문한 적은 있지만, start학생이 원하는 학생이 아직 팀 매칭이 끝나지 않은 학생이라면)
		if (done[next] == 0) {
			for (int i = next; i != start; i = v[i]) { // 시작 노드로 돌아올 때까지 사이클을 따라 이동
				cnt++; // 사이클에 포함된 노드의 수를 증가
			}
			cnt++; // 사이클 시작 학생 추가(시작 노드도 사이클에 포함되므로 노드 수를 하나 더 증가)
		}
	}

	done[start] = 1; // 시작 노드를 처리했다고 표시
}

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

	cin >> T; // 테스트 케이스의 수를 입력 받음

	while (T--) // 각 테스트 케이스에 대해
	{
		cin >> n; // 노드의 수를 입력 받음
		v.resize(n + 1, 0);
		visited.resize(n + 1, false);
		done.resize(n + 1, 0);
		for (int i = 1; i <= n; i++) {
			cin >> v[i]; // 각 노드에서 다른 노드로의 링크를 입력 받음
		}

		cnt = 0; // 사이클에 포함된 노드의 수를 초기화
		for (int i = 1; i <= n; i++) {
			if(visited[i] == false) { // 아직 방문하지 않은 노드에 대해
				DFS(i); // DFS를 호출하여 사이클을 찾음
			}
		}

		cout << n - cnt << "\n"; // 사이클에 속하지 않는 노드의 수를 출력
	
    	// 다음 테스트 케이스를 위해 벡터를 초기화
		v.clear(); 
		visited.clear();
		done.clear();
	}

	return

 

주어진 그래프에서 사이클을 찾고, 사이클에 속하지 않는 노드의 수를 구하는 코드다. 각 노드는 다른 노드로의 단방향 링크를 가지고 있다.

• 사이클에 속하는 노드를 찾을 때 DFS를 사용한다.
• 'visited'와 'done'이라는 두 벡터를 사용하여 각 노드의 상태를 추적한다.
  • 'visited'는 각 노드가 DFS 과정에서 방문되었는지를 파악
  • 'done'은 각 노드가 이미 처리되었는지를 파악
  • 이 두 가지 상태를 통해 사이클을 파악한다.

---

 

 

코딩 스타일에 따른 표기 차이

 

for (int i = next; i != start; i = v[i]) { 
	cnt++;
}

 

 

int i = next;
while (i != start) { 
    cnt++; 
    i = v[i];
}

 

 

위의 두 가지 모두 같은 뜻이다. 표기 차이