[G4] 백준 22856번 트리 순회 C++ 깊이 우선 탐색, 트리

리뷰

 

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

중위 우선 순회를 통해 마지막 노드를 구한 후 주어진 조건에 따라 트리를 탐색하는 횟수를 구하는 문제

전위, 중위, 후위 탐색의 개념을 너무 오랜만에 접해서 문제 이해가 좀 힘들었다.

 

 

전역 변수

• Child : 현재 노드의 좌 우 자식 노드를 정의하기 위한 구조체
• v : 노드 방문 처리를 위한 논리형 배열
• par : 부모 노드 정보를 저장하기 위한 정수형 배열
• n : 주어지는 노드의 개수를 저장할 변수
• en : 중위 순회의 마지막 노드를 저장하기 위한 변수
• ans : 정답을 저장하기 위한 변수
• nodes : 자식 정도를 저장하기 위한 Child 타입의 벡터
• lst : 인접 리스트를 저장하기 위한 정수형 벡터 배열

 

함수

1. find_end

void find_end(int node)

 

중위 순회를 통해 트리 탐색 종료노드를 구하는 함수

1. 매개변수로 노드 번호 node를 전달받는다.
2. 기저 조건으로 노드 번호가 -1이라면 리턴해 준다.
3. find_end 함수에 현재 노드의 왼쪽 자식 노드 번호를 매개변수로 전달하여 재귀를 진행한다.
4. 왼쪽 자식의 재귀를 빠져나온 후 en을 현재 노드의 번호로 저장해 준다.
5. find_end 함수에 현재 노드의 오른쪽 자식 노드 번호를 매개변수로 전달하여 재귀를 진행한다.

 

2. dfs

void dfs(int node)

 

트리를 탐색하며 종료 노드에 도달하기 까지 트리를 탐색하는 횟수를 구하는 함수

1. 매개변수로 노드 번호 node를 전달받고, 아래 로직을 순서대로 체크한 후 먼저 조건에 맞는 로직을 진행한다.
2. 현재 노드의 왼쪽 자식 노드가 -1이 아니고, 방문하지 않았다면 방문처리 및 ans를 증가시키고 재귀를 진행한다.
3. 현재 노드의 오른쪽 자식 노드가 -1이 아니고, 방문하지 않았다면 방문처리 및 ans를 증가시키고 재귀를 진행한다.
4. 현재 노드가 en이라면 탐색을 종료하고 리턴한다.
5. ans를 증가시키고 부모 노드를 dfs함수의 매개변수로 전달하여 재귀를 진행한다.

 

문제풀이

1. n값을 입력 받고, n개의 노드 및 자식 노드 정보를 입력받는다.
2. a의 nodes에 자식 노드 b, c를 순서대로 저장해 준다.
3. b, c의 par에 a의 번호를 저장해 준다.
4. a의 lst에 b, c를 push해준다.
5. 1의 par을 1로 지정해 주고, find_end 함수에 매개변수 1을 전달하여 en을 구해준다.
6. dfs 함수에 매개변수 1을 전달하여 트리를 순회하며 종료 조건 까지 순회한 횟수를 ans에 저장해 준다.
7. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. for문을 통해 인접 리스트를 순회해 보았지만 의미가 없었다.
2. nodes를 통해 좌우 자식 노드를 탐색하는 사이에 en을 최신화 하며 중위 순회를 구현하였다.

 

참고 사항

1. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.
2. 그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 오른쪽 자식 노드로이동한다.
3. 그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.
4. 그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.
5. 유사 중위 순회를 종료할 때까지 1 ~ 4를 반복한다.

en을 중위 순회를 통해 구한 후 위 규칙만 지킨다면 쉽게 구현할 수 있다.

 

정답 코드

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

struct Child {
	int l, r;
};
bool v[100001];
int par[100001];
int n, en, ans;
vector<Child> nodes(100001);

void find_end(int node) {
	if (node == -1) return;
	find_end(nodes[node].l);
	en = node;
	find_end(nodes[node].r);
}

void dfs(int node) {
	if (nodes[node].l != -1 && !v[nodes[node].l]) {
		v[nodes[node].l] = true;
		ans++;
		dfs(nodes[node].l);
	}
	else if (nodes[node].r != -1 && !v[nodes[node].r]) {
		v[nodes[node].r] = true;
		ans++;
		dfs(nodes[node].r);
	}
	else if (node == en) return;
	else {
		ans++;
		dfs(par[node]);
	}
}

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

	cin >> n;
	while (n--) {
		int a, b, c; cin >> a >> b >> c;
		nodes[a] = { b, c };
		par[b] = a;
		par[c] = a;
	}
	par[1] = 1;
	find_end(1);
	dfs(1);
	cout << ans;
}