[C++] 백준/BOJ - 9466 : 텀프로젝트

문제 이해 단계

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

1~n번까지 사람이 있고 선택을 한다. (자기 자신도 선택 가능)

조가 이루어지는 경우는, 꼬리 잡기처럼 1 -> 2 -> 3  -> 1
이런 식으로 사이클을 이를 경우이다.

즉, 마지막에는 자기 자신으로 꼭 돌아와야 한다.

이러한 조건일 때,  짝을 이루지 못한 학생 수를 출력하는 문제이다.

 

---

문제 접근 단계

문제 이해 단계에서 말했듯이, 꼬리 잡기와 비슷한 패턴이다.

꼬리에 꼬리를 물어 추적을 하는 것이다.
이를 돌려 말하면 점점 깊이 들어간다고 할 수 있는데,

그래서 이 문제는 DFS로 푸는 것이 적절하다고 생각했다.

이 문제에서 짝이 이루어지는 경우는 사이클이 형성될 때이다.

처음 선택했던 사람의 번호를, 마지막 사람이 선택할 때 사이클이 형성되므로
(처음 선택했던 사람의 번호) == (마지막 사람이 선택한 사람의 번호)의 참 거짓을 판단한다.

이후에는 조원들의 번호를 저장해 두는 것이 중요하므로
리스트를 사용하여 저장해 두었다.

이에 관한 로직은 문제 구현 단계에서 설명하겠다.

이 문제를 해결하는 것에 대한 핵심은

1. 이 문제가 DFS임을 아는가
2. 조를 형성하는 경우를 어떻게 구현할 것인가
3. 조를 형성할 때 그 조원들을 어떻게 구할 것인가

이 3가지였던 것 같다.

 

---

문제 구현 단계

vector<int> list;
vector<int> answerList;

int Dfs(int x) {
	if (c[x]) return x;
	c[x] = true;
	int y = Dfs(map[x]);
	list.push_back(x);
	if (x == y) {
		for(int i = 0; i < list.size(); i++){
			int v = list[i];
			answerList.push_back(v);
		}
	}
	return y;
}

핵심이 되는 Dfs함수이다.
매개변수로 선택을 하는 사람을 받는다.

y는 선택받은 사람을 뜻하는 변수이다.

Dfs(map [x])를 저장하는데 이를 끝까지 호출하면,
마지막 번호의 선택을 받은 사람의 정보가 y에 저장될 것이다.

이 y 값을 자신을 호출했던 함수
즉, 사람들과 비교해서 일치하는지를 확인하면서 list에 추가한다.

만약 일치한다면, 리스트에 있는 모든 사람을 answerList에 저장한다.

for (int i = 1; i <= n; i++) {
			if (!c[i]) {
				Dfs(i);
				list.clear();
			}
		}

이 Dfs를 1번부터 n번까지 모두 돌리는데
한번 돌릴 때마다 list를 계속 초기화해 준다.

마지막으로 전체코드를 올리고 끝내겠다.

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

int map[100001];
bool c[100001] = { false };
vector<int> list;
vector<int> answerList;

int Dfs(int x) {
	if (c[x]) return x;
	c[x] = true;
	int y = Dfs(map[x]);
	list.push_back(x);
	if (x == y) {
		for(int i = 0; i < list.size(); i++){
			int v = list[i];
			answerList.push_back(v);
		}
	}
	return y;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) c[i] = false;
		for (int i = 1; i <= n; i++) cin >> map[i];

		for (int i = 1; i <= n; i++) {
			if (!c[i]) {
				Dfs(i);
				list.clear();
			}
		}
		cout << n - answerList.size() << "\n";
		answerList.clear();
	}
}

n에서 빼주는 이유는 여기서 구한 answerList는 조를 완성한 인원수이고,
구해야 하는 것은 조를 이루지 못한 인원수이기 때문이다.

 

---

시행착오

기본적으로 Dfs는 재귀함수를 사용해야 해서 난도가 높은 것 같다.

게다가 이번에는 노드들의 정보까지 기억해야 하는 문제였기 때문에
더더욱 구현하기 어려웠던 것 같다.

그래도 한번 구현해 봤으니까 지금보다는 수월하게 풀 수 있지 않을까?