백준 15900 [C++]

www.acmicpc.net/problem/15900

15900번: 나무 탈출

1. 풀이방법

 

- 트리 구조를 이용한 DFS문제 입니다.

 

- 처음에 문제를 읽으면서 가장 고민이 되었던 건 리프노드는 구별이 가능한데 (간선이 1개뿐인 놈(루트제외))

 

- 리프노드에서 한칸 타고 부모로 올라갔을 때, 그다음 부모노드가 어떤 녀석인지를 판정을 어떻게 해야하나

 

- 고민을 많이하고, 결국 class로 노드를 만들어 포인터를 통해서 인접리스트 방식으로 트리를 구현해야하나 생각

 

- 했었는데, 너무 하기 귀찮아서 다시 문제를 읽어보았는데

 

- 사실 문제가 원하는 출력이 그렇게 복잡하지 않습니다. 이기냐, 지냐 만 출력하는 문제이므로

 

- 사실 각각의 리프노드들로 부터 루트노트(1) 까지 가는 간선의 수 (즉 높이) 들의 합이

 

- 홀수이냐, 아니면 짝수 이냐만 파악하면 문제의 정답을 출력할 수 있었습니다.

 

- 즉 ! 높이만 알면 되므로 리프노드 부터 탐색할 필요가 없이, 루트노드부터 dfs를 통해 리프노드까지 가면 됩니다!!!!

 

- 가장 고민하던 문제가 해결되었습니다. 그 다음 부터는 쉽습니다

 

- 그러므로 vector<int> tree[500001]을 통해 트리의 간선정보를 담고 

 

- bool visitnode[500001] 을통해 위에서 내려오는 부모노드는 방문체크를 하여 dfs탐색에서 제외 시켜줍니다.

 

 

 

 

 

2. 주의사항

 

- 리프노드는 연결된 간선이 무조건 하나!!!! 하지만 여기서 주의할 것은 간선이 하나가 될 수 있는 녀석이 하나 더

 

- 있습니다..>!   바로 루트노드는 간선이 하나만 연결될 수 있습니다. 그러므로 종료조건에 s!=1(루트노드)를 추가

 

- 해주었습니다.

 

 

 

 

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int N;
vector<int> tree[500001]; // 메모리때문에 인접행렬은 x 
bool visitnode[500001];
int totalheight = 0;
//간선이 하나만 존재하면 리프노드


void dfs(int s, int cnt) {
	if (tree[s].size() == 1 && s!=1) { //리프노드
		totalheight += cnt;
		return;
	}
	for (int i = 0; i < tree[s].size(); i++) {
		if (!visitnode[tree[s][i]]) {
			visitnode[tree[s][i]] = true;
			dfs(tree[s][i], cnt + 1);
			visitnode[tree[s][i]] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		tree[tmp1].push_back(tmp2);
		tree[tmp2].push_back(tmp1);
	}
	visitnode[1] = true;
	dfs(1, 0);
	if (totalheight % 2 == 1) cout << "Yes" << "\n";
	else { cout << "No" << "\n"; }
	
	return 0;
}