[백준 BOJ/C++] 2668 숫자 고르기

 

2668번: 숫자 고르기

 

문제를 처음 접하면 아이디어가 잘 떠오르지 않는 어려운 문제이기도 하지만 막상 제대로 파악하고 나면 의외로 간단히 풀 수 있는 문제다.
그래프(Graph)와 관련된 문제이고 사이클(Cycle)을 찾는 문제임을 발견하기만 한다면 그 이후부터는 크게 까다로울 것은 없다.

 

출처 - Baekjoon Online Judge

 

문제는 정체를 알 수 없는 표가 주어지고 여기에서 집합을 찾는다는 표현으로 접근 방법을 어렵게하고 있다.

이 문제의 핵심은 바로 이 표가 그래프로 나타내어질 수 있음을 발견하는 것 그리고 찾고자 하는 집합의 조건이 그래프에서 사이클을 형성하는 노드들임을 발견하는 것이다.

 

 

대놓고 그래프 문제임을 보여주거나 연결과 탐색, 경로와 같이 큰 고민 없이 그래프로 연상할 수 있는 키워드를 사용하는 문제들도 많지만 이렇게 특이한 형태의 그래프 문제도 있을 수 있음을 배우게 해주는 문제다.

 

 

---

 

 

문제의 포인트

 

문제 접근 아이디어
사이클 탐지 알고리즘

 

 

문제 접근 아이디어

 

앞서 이야기한 바와 같이 본 문제가 그래프 문제임을 알아내는 것 만으로 이미 절반은 해결하는 문제다.

문제 파악이 핵심인 만큼 처음 문제를 접하면 어떻게 접근해야할 지 막막해질 수 있게 만들어져있다.

 

 

일단 문제에서 찾을 수 있는 힌트는 2행 N열의 테이블에서 첫 번째 행에서 어떤 특정 값을 선택하면 그 바로 아래행 같은 열의 값이 선택에 영향을 받고 연관되어진다는 점이다.

즉, 이 표에서 데이터들은 각 열 단위로 의미를 가지는 것이다.

 

 

한편 첫 번째행은 정수가 1부터 N까지 마치 index와 같이 순차적으로 배치되어있으며 따라서 입력은 두번째 행의 값만 열 순서대로 받는다.

첫 번째 행이 index로 보이면서 오히려 이 표가 간선정보일 것이라는 상상을 방해하기도 하는데 어쨌든 두 행의 데이터가 모두 1~N 사이의 값을 가진다는 점에서 힌트를 얻을 수도 있다.

 

 

표로 주어진 데이터가 결국 간선 정보이며 각 값이 의미하는 바가 노드일 수 있다는 접근을 해보고 손으로 그래프를 그려본다면 문제가 숨기고 있는 데이터의 정체와 찾고자 하는 바가 명확해진다.

아래 그림처럼 예제에서 선택되어야 하는 열과 그 데이터를 통해서 시각적인 힌트를 얻을 수도 있을 것이다.

결과적으로 위와 같은 그래프 형태의 표현을 발견할 수 있다면 문제에서 요구하는 내용이 사이클을 구성하는 노드들을 찾는 것임을 알 수 있다.

 

 

첫째줄과 둘째줄에서 같은 값을 가지는 집합을 만들 수 있는 열을 선택한다는 것은 즉 몇개의 간선을 모아 출발점들의 집합과 도착점들의 집합을 같게 만든다는 의미이다.

결국 몇개의 간선을 지나서 시작점으로 다시 돌아갈 수 있는 사이클을 찾아야 이것이 가능해진다.

 

 

또한 뽑힌 정수의 개수를 최대로 하기 위해서는 출발지와 도착지가 같은 간선 즉, 다른 노드를 거치지 않고 혼자 사이클을 만드는 노드까지 포함해야 한다는 이야기다.

 

 

이제 문제에서 주어지는 데이터와 요구하는 바가 무엇인지 파악했다.

그래프에서 사이클을 탐지하는 방법만 안다면 그대로 답을 찾아주기만 하면 된다.

 

 

사이클 탐지 알고리즘

 

일반적으로 그래프 내에서 사이클을 탐지하는 방식을 그대로 적용하되 사이클에 포함되는 노드들의 수와 그 노드들의 번호를 구해주기만 하면 된다.

 

 

그래프 내에서 사이클이 만들어졌는지 확인하는 방법은 의외로 간단하다.

특정 한 노드를 기준으로 깊이 우선 탐색을 통해 인접한 노드들을 탐색시키면서 탐색 중 이미 방문했던 노드에 다시 방문하는지 확인하면 사이클 유무를 알 수 있다.

 

 

보통 사이클 존재 자체만 확인할 때 그래프 전체를 한번씩 방문하면서 visit 배열을 이용해 이미 방문했던 노드들을 체크하고 중복 방문이 감지되면 탐색을 종료시킨다.

return 처리등 적절한 처리를 통해 사이클이 존재하는지 확인할 수 있다.

 

 

본 문제에서는 사이클을 이루는 노드를 확인해야하기 때문에 똑같은 방법으로 탐색시키다 중복 방문이 감지되면 별도의 중복 탐색을 통해 어떤 노드들이 사이클에 관여하는지 확인할 수 있다.

처음 중복이 감지된 노드를 시작으로 다시 해당 노드로 돌아올 때 까지 지나가는 노드들을 체크해주면 된다.

 

 

void DFS(int n) {
	int next;
    
	next = ARR[n];
	visit[n] = 1;

	if (visit[next] == 0) {
    // 중복 X, 계속 탐색
		DFS(next);
	}
	else {
    // 중복 O, cycle 탐색
		if (check[next] == 0) {
			while (next != n) {
           		// 별개의 while loop로 cycle 에 포함되는 노드들을 탐색
				cnt++;
				check[next]++;
				next = ARR[next];
			}
			cnt++;
			check[n]++;
		}
	}
	check[n]++;
}

 

 

본 문제에서는 cycle에 포함되는 노드들을 오름차순으로 출력해주어야 한다.

따라서 중복을 탐색할 때 위 코드와 같이 별도의 check 배열을 만들어 노드 번호를 index로 중복 여부를 기록해주어 노드번호를 찾을 수 있게 했다.

 

 

이렇게 기본적인 DFS를 조금 변형하면 그래프 내에 사이클이 있는지, 몇개의 노드가 사이클을 만드는지, 어떤 노드들인지 등의 정보를 찾는데 활용할 수 있다.

 

 

그래프에서 사이클이 있는지 확인하는 것은 트리의 정의와도 연결되기 때문에 여러 문제에서 활용될 수 있다.

반드시 그 방법을 숙지해두어야 하겠다.

 

 

---

 

 

전체 Code

 

#include <iostream>

using namespace std;

int N, cnt;
int ARR[100 + 10];
int visit[100 + 10];
int check[100 + 10];

void printCheck() {
	int i;

	for (i = 1; i <= N; i++) {
		if (check[i] > 1)
			cout << i << "\n";
	}
}

void DFS(int n) {
	int next;

	next = ARR[n];
	visit[n] = 1;

	if (visit[next] == 0) {
		DFS(next);
	}
	else {
		if (check[next] == 0) {
			while (next != n) {
				cnt++;
				check[next]++;
				next = ARR[next];
			}
			cnt++;
			check[n]++;
		}
	}

	check[n]++;
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i;

	cin >> N;

	for (i = 1; i <= N; i++) {
		cin >> ARR[i];
	}

	for (i = 1; i <= N; i++) {
		if (visit[i] == 0) {
			DFS(i);
		}
	}

	cout << cnt << "\n";
	printCheck();

	return 0;
}