[G5] 백준 19641번 중첩 집합 모델 C++ 트리, 오일러 경로 테크닉, 트리셋

리뷰

 

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

오일러 경로 테크닉의 기초적인 문제이다.

 

 

전역 변수

• N : 배열 크기의 최대 값을 저장할 상수 변수
• n : 정점의 개수를 저장할 변수
• s : 트리의 루트를 저장할 변수
• lst : 인접 리스트를 저장할 정수형 트리셋 배열
• it : inTime을 저장할 배열
• ot : outTime을 저장할 배열
• t : Time을 저장할 변수
• v : 방문 여부를 체크할 배열

 

함수

1. dfs

void dfs(int node)

 

깊이 우선 탐색을 통해 it, ot배열을 초기화 하기 위한 함수

1. 매개 변수로 현재 노드의 번호 node를 전달 받는다.
2. it배열의 node인덱스에 t를 전위증가 시킨 값을 저장한다.
3. node의 인접 리스트를 순회하며 방문처리가 되어 있지 않으면 방문처리 후 재귀를 진행한다.
4. 모든 탐색과 재귀를 빠져나온 후 ot배열의 node인덱스에 t를 전위증가 시킨 값을 저장한다.

 

문제풀이

1. n값을 입력 받고, n개의 노드에 인접 리스트를 최신화 해준다.
2. s값을 입력 받고, s에 방문처리 후 dfs함수에 매개변수로 s를 전달하여 it, ot배열을 초기화 한다.
3. 1 ~ n번의 노드를 순회하며 it, ot에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. vector에 인접리스트를 초기화 하고 예제가 맞는 걸 확인 후 제출하였다가 Fail을 받았다.
2. "번호가 가장 낮은 노드부터 오름차순으로 방문해야 한다"는 조건 확인 후 vector를 set으로 변경하여 AC를 받았다.

 

참고 사항

• 문제의 조건에 맞게 ot를 기록할 때도 t를 전위증가 시켜주어야 한다.

 

정답 코드

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

const int N = 100001;
int n, s;
set<int> lst[N];
int it[N];
int ot[N];
int t;
bool v[N];

void dfs(int node) {
	it[node] = ++t;
	for (int i : lst[node]) {
		if (v[i]) continue;
		v[i] = true;
		dfs(i);
	}
	ot[node] = ++t;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int node; cin >> node;
		while (1) {
			int v; cin >> v;
			if (v == -1) break;
			lst[node].insert(v);
		}
	}
	cin >> s;
	v[s] = true;
	dfs(s);
	for (int i = 1; i <= n; ++i) {
		cout << i << " " << it[i] << " " << ot[i] << "\n";
	}
}