11725 트리의 부모 찾기 - c++

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

11725번: 트리의 부모 찾기

 

너무 오랜만에 풀어서 노드의 연결 정보로 트리를 만드는 방법도 까먹었다..

 

트리를 만드는 방법은 크게 인접 행렬, 인접 리스트가 있는데, 인접 행렬은 정말 직관적인데 비해 인접 리스트는 덜 직관적이라서 코드 쓸때 헷갈리다는 점을 제외하곤 반복문을 덜 돌아서 효과적이다. 이 경우는 100000이라서 인접 리스트로 해결함. (앞으로도 그냥 계속 인접 리스트로 연습해야겠다. 쨋든 확실히 인접 행렬보다는 더 좋으니까)

 

이 경우 노드와 바로 연결된 부모를 물어보는 것이므로, 루트부터 마지막 노드까지 한번에 가는 DFS보다는 부모와 연결된 자식을 큐에 바로바로 추가하는 BFS가 적합하다고 생각하고 풀었다. 

 

또, 그냥 STL 큐를 사용해도 되는데 연습 겸 직접 큐를 구현하면서 풀었다.

 

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, a, b, i, x, front=-1, back=-1;
	cin>>n;
	vector<int> m[n+2], Q(n+2), ch(n+2), parent(n+2);
	for(int i=1; i<=n-1; i++) {
		cin>>a>>b;	
		m[a].push_back(b);
		m[b].push_back(a);
	}
	Q[++back] = 1;
	ch[1] = 1;
	parent[1] = 1;
	while(front < back) {
		x = Q[++front];
		for(i=0; i<m[x].size(); i++) {
			if(ch[m[x][i]] == 0) {
				ch[m[x][i]] = 1;
				parent[m[x][i]] = x;
				Q[++back] = m[x][i];
			}
		}
	}
	for(int i=2; i<=n; i++) {
		cout<<parent[i]<<"\n";
	}
	return 0;
}

 

하면서 중간에 막혔던 부분들

• 큐 안에서 ch배열 빼고 해봐도 괜찮지 않을까?라고 생각하고 처음에 뺐더니 무한루프를 돌고 있었다.. 무방향 그래프면 자식도 부모노드를 넣거늘... 다시는 빼먹지말자 ㅠㅠ
• m, Q, ch, parent 배열의 크기를 n+1로 할때는 OutOfBounds 런타임 에러가 발생했으나, n+2로 할때는 발생하지 않았다. 왜 그랬는지는 아직은 모르겠다!