[BOJ][11725] 트리의 부모 찾기

1. 문제 링크

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

2. 사용 알고리즘

트리, BFS

3. 풀이

단계별로 진행한다는 BFS의 성질을 이용

1) 연결 상태를 저장하기 위한 arr 배열, 방문여부를 저장하기 위한 check 배열, 부모 노드를 저장하기 위한 parent 배열, BFS 탐색을 위한 큐 선언

2) 1번 노드를 큐에 저장 후 1번 노드부터 BFS 탐색 시작

3) 1번 노드와 연결된 노드의 부모 노드를 1로 설정

4) 큐가 비어있지 않은 동안 2) ~ 3)의 과정 반복

5) parent 배열의 값 차례대로 출력

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/11725.cpp

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

using namespace std;

vector<int> arr[100003];
int check[100003];
int parent[100003];
queue<int> q;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    for(int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        arr[u].push_back(v);
        arr[v].push_back(u);
    }
    q.push(1);
    check[1] = 1;
    while(!q.empty()) {
        int p = q.front();
        q.pop();
        int len = arr[p].size();
        for(int i = 0; i < len; ++i) {
            int num = arr[p][i];
            if(!check[num]) {
                q.push(num);
                parent[num] = p;
                check[num] = 1;
            }
        }
    }
    for(int i = 2; i <= n; ++i) {
        cout << parent[i] << "\n";
    }
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/11725.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    
    static ArrayList<Integer>[] arr = new ArrayList[100003];
    static Queue<Integer> q = new LinkedList<>();
    static int[] parent = new int[100003];
    static int[] check = new int[100003];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; ++i) arr[i] = new ArrayList<>();
        StringTokenizer st;
        for(int i = 0; i < n - 1; ++i) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arr[u].add(v);
            arr[v].add(u);
        }
        q.add(1);
        check[1] = 1;
        while(!q.isEmpty()) {
            int p = q.remove();
            int len = arr[p].size();
            for(int i = 0; i < len; ++i) {
                int num = arr[p].get(i);
                if(check[num] == 0) {
                    q.add(num);
                    parent[num] = p;
                    check[num] = 1;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 2; i <= n; ++i) {
                sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
    }
}