[BOJ] 2668 - 숫자고르기

안녕하세요.

여행벌입니다.

오늘은 백준 사이트 2668번 '숫자고르기' 문제를 다뤄보겠습니다.

정보올림피아드 초등부 문제로 DFS 탐색을 이용해서 구현할 수 있었습니다.

---

[알고리즘설계]

1. 입력된 정수를 list에 담고 앞에서부터 다음과 같이 탐색을 진행한다.

- 아직 방문하지않은 점이라면 Cycle이 형성되거나 이미 탐색한 점이 나올때까지 탐색을 진행한다.

 -> Cycle이 형성되었다면, Cycle의 크기만큼 Count 해주고, Cycle에 속한 숫자들을 Answer_list에 담아준다.

( Cycle의 형성 유무는 탐색을 하며 지나왔던 숫자와 다음에 가야할 숫자를 비교하며 판단한다. )

 -> 이미 탐색한 점이 나왔다면, 기존에 탐색한 루트이므로 종료한다.

2. 모든 점에 대한 탐색이 끝났다면, Answer_list를 Sort 한 후 앞에서부터 출력해준다.

 

[예시]

Index [ 1 2 3 4 5 6 7 ]

Input [ 3 1 1 5 5 4 6 ]

1 -> 3 -> 1 (Cycle 형성, 1,3을 Answer_list에 담아준다.)

2 -> 1 ( 1은 이미 방문한 점이므로 탐색을 종료한다. )

3 ( 1에서 탐색을 진행할 때 이미 방문한 점이므로 탐색을 종료한다. )

4 -> 5 -> 5 (Cycle 형성, 5를 Answer_list에 담아준다.)

5 ( 4에서 탐색을 진행할 때 이미 방문한 점이므로 탐색을 종료한다. )

6 -> 4 ( 4는 이미 방문한 점이므로 탐색을 종료한다. )

7 -> 6 ( 6은 이미 방문한 점이므로 탐색을 종료한다.

 

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

int answer[100], nanswer = 0;
int list[101];
bool check[101];
int check_circle(int, int, int[]);
void circle(int);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
    
	int ninput;
	cin >> ninput;
	for (int i = 1; i <= ninput; i++)
		cin >> list[i];
        
	for (int i = 1; i <= ninput; i++) {
		if(check[i] == false) //방문하지않은점이라면 탐색 시작.
			circle(i);
	}
    
	cout << nanswer << '\n';
	sort(answer, answer + nanswer);
	for (int i = 0; i < nanswer; i++)
		cout << answer[i] << '\n';
}

int check_circle(int next, int count, int temp[]) {
	int i;
	for (i = count - 1; i >= 0; i--) {
		if (temp[i] == next) {
			return i;
		}
	}
	return -1;
}

void circle(int i) {
	int temp[100];
	int start = i;
	check[start] = true;
	int count = 0;
	temp[count++] = start;
	while (1) {
		int next = list[start];
		int ntemp = check_circle(next, count, temp);
		if (ntemp != -1) {
			for (int j = ntemp; j < count; j++) {
				answer[nanswer++] = temp[j];
			}
			return;
		}
        // 기존에 방문한 점이라면 종료.
		if (check[next] == true)
			return;
		start = next;
		check[start] = true;
		temp[count++] = start;
	}
}

초등부 문제라 입력은 작지만, 구현이 생각보다 까다로웠던 문제입니다. 

비슷한 문제로는 BOJ 9466번을 추천드립니다!

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.