[백준 / C언어] 2668번: 숫자고르기 (DFS로 풀이)

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

2668번: 숫자고르기

난이도: solved.ac 골드 5

 

알고리즘 분류

---

그래프 탐색, DFS (깊이 우선 탐색)

 

접근 방법

---

방향이 있는 그래프로 생각하면 쉽다. 사이클이 있는 노드들의 개수를 세는 문제다.

문제에 있는 표에서 1행의 숫자들을 노드라고 생각하고, 2행에 있는 숫자들을 1행에 있는 노드에서 연결된 노드라고 보면 된다.

 

구현

---

1번 노드부터 N번 노드까지 각 노드를 시작점으로 해서 화살표를 따라가 사이클이 생기는지 확인한다.

방문한 노드는 visited에 1로 표시를 해주는데, 화살표를 계속 따라가다가 방문한 노드로 돌아오게 되면 이는 사이클이 생겼다는 걸 의미한다.

 

예를 들어, 1번 노드를 시작점으로 화살표를 계속 따라갔을 때 아래와 모습이 그려진다고 해보자.

6번 → 3번 → 5번 → 6번 노드로 사이클이 생긴다. 여기서 visited에는 1번, 4번, 6번, 3번, 5번 노드가 1로 표시되어 있을 텐데 여기서 사이클이 생긴 부분만 남기고 나머지는 지운다. 따라서 다시 시작점인 1번으로 돌아가 사이클이 시작되는 6번 노드까지의 길을 삭제한다.

 

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int graph[101];
int visited[101];

void find(int start);

int main() {
	int N, i, cnt = 0;
	int ans[100];

	scanf("%d", &N);
	for (i = 1; i <= N; i++)
		scanf("%d", &graph[i]);
	
	for (i = 1; i <= N; i++) {
		if (!visited[i]) {
			find(i);
		}
	}

	for (i = 1; i <= N; i++) {
		if (visited[i]) {
			ans[cnt] = i;
			cnt++;
		}
	}

	printf("%d\n", cnt);
	for (i = 0; i < cnt; i++)
		printf("%d\n", ans[i]);
	return 0;
}

void find(int start) {
	int num = start;
	// 사이클 탐색
	while (!visited[num]) {
		visited[num] = 1;
		num = graph[num];
	}
	// 사이클 전까지의 노드 visited에서 제거
	while (start != num) {
		visited[start] = 0;
		start = graph[start];
	}
}