백준 11725 - 트리의 부모 찾기

문제

 

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

11725번: 트리의 부모 찾기

 

 

풀이

 

각 노드의 부모를 저장하기 위해 p[] 배열을 만들어서 여기에 저장한다. 트리도 그래프이므로 그래프의 탐색을 이용해서 노드의 부모를 찾는 과정을 가진다. 문제에서 루트 노드가 1이므로 1부터 그래프 탐색을 시작하면 1과 연결된 다음에 방문할 노드들은 부모가 1이 된다. 

 

따라서 다음에 방문할 노드의 부모 노드는 현재 노드가 된다. 

 

 

코드

c++

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> tree[100001];
bool visit[100001];
int p[100001];
int N;
 
void dfs(int x, int pn)
{
    visit[x] = true;
    p[x] = pn;
 
    for (int i=0; i<tree[x].size(); i++)
    {
        int next = tree[x][i];
        if (!visit[next]) dfs(next, x);
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N;
 
    int from, to;
    for (int i=0; i<N-1; i++)
    {   
        cin >> from >> to;
        tree[from].push_back(to);
        tree[to].push_back(from);
    }
 
    dfs(1, 0);
 
    for (int i=2; i<=N; i++) cout << p[i] << '\n';
 
    return 0;
}

 

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static int n;
    static List<List<Integer>> list;
    static int[] parents;
    static boolean[] visited;

    public static void main(String[] args) {
        input();
        solve();
    }

    private static void solve() {
        dfs(1, 1);
        for (int i = 2; i <= n; i++)
            System.out.println(parents[i]);
    }

    private static void dfs(int x, int parent) {
        visited[x] = true;
        parents[x] = parent;

        for (int next : list.get(x)) {
            if (!visited[next])
                dfs(next, x);
        }
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        parents = new int[n + 1];
        visited = new boolean[n + 1];
        list = new ArrayList<>();

        for (int i = 0; i <= n; i++)
            list.add(new ArrayList<>());

        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            list.get(a).add(b);
            list.get(b).add(a);
        }

        sc.close();
    }
}