(2) [C++, Java] 백준 No.11725 : 트리의 부모 찾기

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터7-3-트리-문제풀이

# C++(DFS, 인접리스트를 이용한 풀이)

#include <iostream>
#include <vector>

using namespace std;

int e;                              // 간선의 개수
vector<int> vec[100001];            // 인접리스트
bool check[100001];                 // check배열
int parent[100001];
void dfs(int x);

int main()
{
    //정점의 개수
    cin >> e;

    //입력을 받아 인접리스트 만들기
    for (int i = 0; i < e-1; i++){
        int a, b;
        cin >> a >> b;
        // 주어진 간선이 양방향이라고 하였으므로
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    //인접리스트를 이용해서 DFS탐색하기
    dfs(1);

    for (int i = 2; i <= e; i++)
        cout << parent[i] << "\n";
}

void dfs(int x){
    //cout << x << " ";
    check[x] = true;

    for (int i = 0; i < vec[x].size(); i++){
        if (check[vec[x][i]] == false){
            parent[vec[x][i]] = x;
            dfs(vec[x][i]);
        }
    }
}

 

# C++(BFS, 인접리스트를 이용한 풀이)

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

using namespace std;

int e;                              // 간선의 개수
vector<int> vec[100001];            // 인접리스트
bool check[100001];                 // check배열
int parent[100001];
void bfs(int x);

int main()
{
    //정점의 개수
    cin >> e;

    //입력을 받아 인접리스트 만들기
    for (int i = 0; i < e-1; i++){
        int a, b;
        cin >> a >> b;
        // 주어진 간선이 양방향이라고 하였으므로
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    //인접리스트를 이용해서 BFS탐색하기
    bfs(1);

    for (int i = 2; i <= e; i++)
        cout << parent[i] << "\n";
}

void bfs(int x){
    queue<int> q;

    q.push(x);
    check[x] = true;

    while(!q.empty()){
        int currentNode = q.front();
        q.pop();
        //cout << currentNode << " ";
        for (int i = 0; i < vec[currentNode].size(); i++){
            if(check[vec[currentNode][i]] == false){
                q.push(vec[currentNode][i]);
                check[vec[currentNode][i]] = true;
                parent[vec[currentNode][i]] = currentNode;
            }
        }
    }
}

 

# Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = new ArrayList<Integer>();
        }
        for (int i=0; i<n-1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            a[u].add(v);
            a[v].add(u);
        }
        boolean[] check = new boolean[n+1];
        int[] parent = new int[n+1];
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        check[1] = true;
        while (!q.isEmpty()) {
            int x = q.remove();
            for (int y : a[x]) {
                if (check[y] == false) {
                    check[y] = true;
                    parent[y] = x;
                    q.add(y);
                }
            }
        }
        for (int i=2; i<=n; i++) {
            System.out.println(parent[i]);
        }
    }
}