[백준 BOJ][C++]11725번 트리의 부모 찾기 풀이: BFS/DFS

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

11725번: 트리의 부모 찾기

 

 이 문제는 BFS를 사용하여 해결할 수 있습니다. 

 

 [풀이 과정]

1. 입력된 엣지 정보로 그래프 만들기

2. queue에 루트 노드 1 push

3. queue에서 하나씩 pop해서 자식 노드 검사

4. 자식 노드를 아직 방문하지 않았다면 ans[자식]=부모, 자식 노드 방문 표시, queue에 자식 노드 push

5. queue가 empty일 때까지 3. 과 4. 반복

 

 

 먼저 그래프를 만들어야 하는데 2차원 배열로 그래프를 생성하게 되면 N의 MAX 값인 100000을 제곱한 만큼의 크기를 만들 수 없으므로 vector를 사용하여 그래프를 생성합니다. 

#include<vector>

#define MAX 100001

vector<int> graph[MAX];

 

 이제 주어진 입력 값으로 그래프 정보를 저장하겠습니다. 

 

 graph[n] 은 노드 n에 연결된 모든 노드를 저장하는 vector입니다. 

for(int i=0; i<N-1; i++){
	int u, v;
    	cin >> u >> v ;
    	graph[u].push_back(v);
    	graph[v].push_back(u);
}

 

이제 BFS를 통해 탐색을 해나가며 각 노드의 부모 노드를 세팅해주면 되는데요.

 

예제를 보겠습니다.

 

7

1  6

6  3

3  5

4  1

2  4

4  7

 

다음 입력 예제와 같이 주어지면 graph는 다음과 같이 됩니다. 

	vector<int> graph[n]
graph[1]	{6, 4}
graph[2]	{4}
graph[3]	{6, 5}
graph[4]	{1, 2, 7}
graph[5]	{3}
graph[6]	{1, 3}
graph[7]	{4}

먼저 queue<int> q에 루트 노드 1을 push 해줍니다. 

 

이제 while문을 통해 queue가 empty일 때까지 탐색을 시작합니다. 

 

q에서 pop할 원소는 자식 노드를 검사할 부모 노드입니다. int parent=q.front() 라고 하겠습니다. 

 

현재 queue는 다음과 같습니다. 

 

queue
1

 

visit
1	0	0	0	0	0	0

ans
0	0	0	0	0	0	0

 

(1) temp=1

 

queue에서 pop 했으니 현재 queue는 비어있겠죠!

 

이제 노드 1에 연결된 노드들 중 자식 노드를 검사합니다. 

 

 노드 1에 연결된 노드들은 graph[1]={6, 4}이고 6과 4 모두 아직 방문하지 않았죠!

 

 두 노드 모두 방문 표시와 queue에 push를 해주고 부모 노드 1을 저장시킵니다. 

 

queue
	6	4

 

visit
1	0	0	1	0	1	0

ans
0	0	0	1	0	1	0

 

 

(2) temp=6

 

이제 노드 6에 연결된 노드들 중 자식 노드를 검사해봅시다. graph[6]={1, 3} 입니다. 

 

노드 1은 이미 방문했기 때문에 아무것도 하지 않습니다. 반면 노드 3은 아직 방문하지 않았죠!

 

 노드 3을 방문 표시와 queue에 push한 뒤 노드 3에 대한 부모 노드를 저장합니다. 이때 부모 노드는 현재 노드인 6이겠지요~~

 

queue
		4	3

visit
1	0	1	1	0	1	0

ans
0	0	6	1	0	1	0

 

이 과정을 queue가 empty일 때까지 진행해주시면 됩니다! 표로 보니까 이해하기 쉽죠~~!

 

 

다음은 전체 코드입니다. 

 

#include <iostream> 
#include <vector> 
#include <queue>

using namespace std; 

#define MAX 100001 
int N; 
int ans[MAX]; 
bool visit[MAX]; 
vector<int> graph[MAX]; 

void bfs(){
    queue<int> q;
    visit[1]=true;
    q.push(1);
    
    while(!q.empty()){
        int parent=q.front();
        q.pop();
        
        for(int i=0; i<graph[parent].size(); i++){
            int child=graph[parent][i];
            if(!visit[child]){
                ans[child]=parent;
                visit[child]=true;
                q.push(child);
            }
        }
    }
}

int main() {
    cin >> N; 
    for(int i=0;i<N;i++) { 
        int x,y; 
        cin >> x >> y; 
        graph[x].push_back(y); 
        graph[y].push_back(x); 
    } 
    
    bfs(); 
    
    for(int i=2;i<=N;i++) 
        cout << ans[i] << "\n"; 
}