[BOJ/백준] 11725 트리의 부모 찾기

● [문제번호 11725] 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

● 알아야 할 것

: vector 자료구조와 메소드

: 그래프

: 트리

: DFS, BFS

 

 

● 풀이 과정

: BFS, DFS(재귀) 각각 구현했는데 중요한 로직은 동잃하다.

 

1. 모든 노드의 연결관계를 입력받고

 

2. DFS(재귀), BFS를 이용하여 모든 노드의 부모노드를 저장한다.

→ 현재노드의 자식노드들의 부모노드는 자신이다.

 

3. 저장한 각 노드의 부모노드를 출력한다,

 

 

● 주의 할 것

: 찾는 노드를 입력하면 부모노드를 반환하는 함수를 만들어

모든 노드를 함수에 한번씩 넣었더니

'시간 초과'가 나왔다.

 

생각해보니 중복된 탐색 실행을 하는 것보다

한번에 각 노드의 부모노드를 저장하면 시간이 줄어들겠다는 생각으로

배열에 따로 저장하여 구현했다.

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// graph : 각 정점(index)의 연결된 정점을 저장
// visited : 부모노드를 방문하지 않기 위해 만든 방문기록
// parent : 각 정점(index)의 부모노드 저장
vector<int> graph[100001];
bool visited[100001];
int parent[100001];
int N;

// 1을 부모노드라 가정할 때
// 모든 정점의 부모노드 저장
// 깊이 우선 탐색
void DFS(int p)
{
    for(int c = 0; c < graph[p].size(); c++)
    {
        int child = graph[p][c];
        
        if(!visited[child])
        {
            // 1. 방문체크인
            // 2. 자식노드의 부모노드 저장
            // 3. 자식노드로 재귀
            visited[child] = true;
            parent[child] = p;
            DFS(child);
        }
    }
}

// 너비 우선 탐색
void BFS()
{
    queue<int> q;
    
    visited[1] = true;
    q.push(1);
    
    while(!q.empty())
    {
        int p = q.front();
        
        q.pop();
        
        for(int c = 0; c < graph[p].size(); c++)
        {
            int child = graph[p][c];
            
            if(!visited[child])
            {
                // 1. 방문체크인
                // 2. 자식노드의 부모노드 저장
                // 3. 자식노드로 재귀
                visited[child] = true;
                parent[child] = p;
                q.push(child);
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 그래프 입력
    for(int n = 0; n < N ; n++)
    {
        int a, b;
        
        cin >> a >> b;
        
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    // 모든 정점의 부모노드 저장
    // 두 함수 중 선택하여 실행한다.
    BFS();
    // DFS(1);
    
    // 출력
    for(int i = 2; i <= N; i++)
        cout << parent[i] << "\n";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [620 - 트리 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1991	트리 순회	https://pirateturtle.tistory.com/288
2	2250	트리의 높이와 너비	https://pirateturtle.tistory.com/289
3	11725	트리의 부모 찾기	https://pirateturtle.tistory.com/290
4	1167	트리의 지름	https://pirateturtle.tistory.com/291
5	1967	트리의 지름	https://pirateturtle.tistory.com/292