BOJ 11558 The game of death / C++

문제 링크 : www.acmicpc.net/problem/11558

11558번: The Game of Death

 

DFS 연습 겸 풀어본 문제였는데 생각보다 시간이 오래 걸렸다.

 

처음 제출했을 때 시간초과가 떠서 구글링을 해보았지만 다른 분들이 많이 푼 문제가 아니여서 혼자 해결해야했다.

 

아이디어는 재귀를 사용한 DFS로 풀이를 진행하였는데 부분부분 예외사항들이 많아서 조건절이 꽤 필요했다.

 

예를 들어, 희현이와 주경이가 같은 사람인 경우에도 본인을 가리키면 1, 아니라면 0을 출력해야 한다.

 

따라서 ans == 1 && participants[1] != 1 일 경우에는 0을 출력해주고 본인을 가리키는 경우에는

 

DFS 함수를 거치면 cnt=1이 되므로 신경쓰지 않아도 된다.

 

또, 서로를 가리키는 경우에는 visited[n] == true && n != ans 인 경우이므로, cnt=0으로 만들고 함수를 종료시킨다.

 

그 외에는 DFS의 재귀로 카운트된다. 각 테스트케이스가 끝나면 cnt, participants, visited를 모두 초기화시켜준다.

 

 

 

 

<소스 코드>

#include <iostream>
using namespace std;
int cnt = 0;
int ans;
int participants[10001] = { 0, };
bool visited[10001] = { false, };

int DFS(int n) {
	if (n != ans && visited[n] == false) {
		cnt++;
		visited[n] = true;
		return DFS(participants[n]);
	}
	else {
		if (visited[n] == true && n != ans) {
			cnt = 0;
			return 0;
		}
		else {
			cnt++;
			return 0;
		}
	}
}


int main() {
	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> ans;
		for (int j = 1; j <= ans; j++) {
			cin >> participants[j];
		}

		if (ans == 1 && participants[1] != 1) {
			cout << 0 << '\n';
			continue;
		}
		visited[1] = true;

		DFS(participants[1]);
		cout << cnt << '\n';

		cnt = 0;
		for (int j = 1; j <= ans; j++) {
			participants[j] = 0;
		}
		for (int j = 1; j <= ans; j++) {
			visited[j] = false;
		}
	}
}