[백준 BOJ] 10451_순열 사이클

 

그래프 문제 중 사이클의 개수에 대한 문제이다. 생각보다 어렵지 않게 구현했는데 사이클의 개수를 구하는 부분이 조금 어려웠다. 1 3 5 7의 사이클 개수는 1개인데 방문할 때마다 체크 하면 값이 4가 나오고 그랬다. 

 

특히 재귀에 대한 부분을 해결하는게 관건이었다.  처음엔 void dfs로 했는데 int dfs로 구현하여 return 값을 통해 구해야 할 부분만 구하고 종료시키는 방법을 선택하였다. 

 

• 입력

int size;
cin >> size;
int n;
for (int i = 1; i <= size; i++) {
	cin >> n;
	graph[i].push_back(n);
}

처음에 입력받는 것에 잘못 접근해서 조금 헤맸었다. 입력 값을 정렬하여 새로운 벡터에 넣고 서로 이어줘야 하는지 생각했었다. 하지만 그럴 필요 없이 1,2,3..N번째 인덱스에 각각의 값을 넣어주면 된다.

 

 

• DFS

int dfs(int idx) {
	if (graph[idx][0] == idx) { // 루프인 경우
		visited[idx] = true;
		cnt=1; // 사이클의 개수
		return cnt;
	}
	int next = graph[idx][0];
	if (!visited[next]) {	
		visited[next] = true;
		dfs(next);
		cnt = 1;
		return cnt;
	}
	return 0;
}

 

DFS 자체를 구현하는 것은 크게 어렵지 않았는데 다음과 같은 부분에서 조금 헤맸었다.

---

1. dfs를 재귀 호출한 뒤, dfs(next) 아래의 코드 처리
   • void dfs()로 구현했을때, 1 3 5 7의 사이클의 경우 dfs의 재귀호출이 끝나면 dfs(next) 밑에 있는 코드가 4번 실행되기 때문에 사이클의 개수가 4개로 되고 이랬다.
   • int dfs() 바꾸어 탐색이 끝나면 무조건 사이클은 1개이기 때문에 cnt = 1로 하고 return 해주었다.
2. return 0
   • 이게 없으면 안된다 제일 중요한 부분 중 하나

• 값 계산, 출력, 초기화

for (int i = 1; i <= size; i++) {
	int tmp = dfs(i);
	ans += tmp;
}
cout << ans <<endl;

// 초기화 
for (int i = 1; i <= size; i++) {
	visited[i] = false;
	graph[i].clear();
}
cnt = 0;
ans = 0;

dfs의 리턴 값은 1또는 0인데 1인경우 하나의 사이클이 형성되었다는 의미이므로 ans에 더해준다.

1개의 테스트 케이스에 모든 테스트 케이스가 들어오는 문제이기 때문에 초기화 과정이 꼭 필요하다.