안녕하세요.
여행벌입니다.
오늘은 백준 사이트 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번을 추천드립니다!
열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다!
감사합니다.
'Problem Solving > BOJ' 카테고리의 다른 글
| [BOJ] 1436 - 영화감독 숌 (0) | 2019.08.21 |
|---|---|
| [BOJ] 2456 - 나는 학습회장이다. (0) | 2019.08.21 |
| [BOJ] 2579 - 계단 오르기 (0) | 2019.08.21 |
| [BOJ] 6603 - LOTTO (0) | 2019.08.21 |
| [BOJ] 14503 - 로봇청소기 (0) | 2019.08.16 |
