백준 9466. 텀 프로젝트[실패]

1.실패 원인

정말.. 오류를 알고싶다. 테스트 케이스로 올라온 문제들은 통과됐지만 제출해보니 답이 아니었나보다.

이유는 잘 모르겠다. dfs 문제인 것도 알았고 조건을 어떻게 넣어줘야 할지도 알고있었지만 답이아니었다.

 

2.작성 코드

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

int party[100001];
bool bparty[100001] = { false, };
int n = 0;
int answer = 0;
void dfs(int start,int next) {
	
	
	if (start == next && bparty[next] == true) {
		answer++;
		return;
	}
	if (bparty[next]) {
		return;
	}
	
		bparty[next] = true;
		int ne = party[next];
		dfs(start, ne);
	
}

int main() {

	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		
		cin >> n;
		answer = 0;
		for (int j = 1; j <= n; j++) {
			cin >> party[j];
			
		}

		for (int j = 1; j <= n; j++) {
			
				dfs(j, j);
		}
		
		answer = n - answer;
		cout << answer << endl;
		memset(party, 0, sizeof(party));
		memset(bparty, false, sizeof(bparty));
	
	}

	return 0;
}

3.참고 코드

https://jaimemin.tistory.com/674

백준 9466번 텀 프로젝트

4. 해결 방안

꾸준함님의 코드를 보면 bool[] 변수를 하나 더 두어서 방문을 했지만 끝난 노드가 아닌 경우를 식별한다.

나는 dfs의 매개변수를 통해 start,next를 받아서 start와 next가 같을 때 루프를 식별했다.

이런 방식을 사용하면 맨 처음 노드로부터 연결된 노드들이 꼬리에 꼬리를 물고 다시 처음 노드로 오는경우에

카운트를 셌다. 한 번에 카운팅을 하지 않아 코드 효율성이 떨어지긴 하지만 결국에는 루프에 있는 노드 개수를

정확히 세기 때문에 문제는 없어보인다. 그리고 방문하지 않은경우 dfs를 돌려버리는 것도 신박했다.

 

일단 다른 글들을 보면 왜 그렇게 동작하는지 이해는 가지만.. 정작 내 코드가 안먹히는 이유를 못찾겠다.

이번 문제는 체크를 해뒀다가 다음에 한 번 처음부터 다시 생각해봐야겠다.