백준 11725. 트리의 부모 찾기[실패]

1.실패 원인

문제를 이해하지 못했다. 테스트 케이스의 출력 결과가 왜 그렇게 되는지도 몰랐고.. 무슨 알고리즘을 사용해야할지 감도 안잡혔다. 풀이를 보다가 1,2,3,.. 순서대로 자신의 부모가 출력되는걸 알아차렸다. 처음에는 전위 순회처럼 노드에서부터 내려오면서 자신의 부모가 누구인지 출력하는 문제인줄 알았는데 알고보니 1->n-1까지 진행하면서 출력하는 것이었다. 그리고, dfs는 생각도 안하고있었는데(알고리즘 너무 오랜만에 품 ㅠ) 트리 문제길래 저번에 푼 문제처럼 배열이나 클래스를 만들어야 한다고 생각했다. 

 

결국 이 문제에서 중요한 것은 노드와 노드가 연결되어 있고 그 사이에서의 관계를 통해 답을 유추하는 문제이다. 따라서 연결 요소를 파악하는 문제이기에 dfs를 사용한 것이다.

 

2.작성 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[10001];
bool visit[10001] = { false, };
int parent[10001];
void dfs(int start) {

	
	visit[start] = true;

	for (int i = 0; i < v[start].size(); i++) {
		int next = v[start][i];

		if (!visit[next]) {

		parent[next] = start;
		dfs(next);
		}
	}

}

int main() {

	int n = 0;
	cin >> n;

	for (int i = 0; i < n-1; i++) {
		int k, t;
		cin >> k >> t;
		v[k].push_back(t);
		v[t].push_back(k);

	}

	dfs(1);

	for (int i = 2; i <= n; i++) {
		cout << parent[i] << endl;
	}
	return 0;
}

3.참고 코드

https://jaimemin.tistory.com/585

백준 11725번 트리의 부모 찾기

4. 해결 방안

무섭다.. 이제 문제가 2문제 남았는데 최근에 틀리기만 했다 ㅠ 그래프는 진짜 어려운 것 같다.