[Java] BOJ 11725 트리의 부모 찾기 (트리)

BOJ 11725 S2 트리의 부모 찾기

• 트리
• silver2

🔍 문제 설명

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

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

✔ 입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

✔ 출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

💡 풀이

트리를 구현한다.

    static class Node {
        int id;
        int parent;
        ArrayList<Node> adjList;
        public Node(int id) {
        	this.id = id;
        	this.adjList = new ArrayList<>();
        }
    }

각 Node의 아이디, 부모, 인접 노드들을 저장할 Node 클래스를 사용했다.

값을 초기화 한 후, 입력으로 들어온 두 정점을 양방향 연결한다.
그리고 루트노드에서부터 bfs()로 탐색하여 각 노드의 부모 노드를 찾았다.

루트노드가 1번이므로, 1번 노드부터 탐색을 시작한다.

        while(!q.isEmpty()){
            Node curNode = q.poll();

            for(Node nextNode : curNode.adjList){ 	//curNode의 인접노드들 탐색
                if(visited[nextNode.id]) continue;
                visited[nextNode.id] = true;
                nextNode.parent = curNode.id; //나의 부모를 저장한다. (내가 curNode로부터 왔기 때문)
                q.add(nextNode);
            }
        }

현재 노드를 curNode라고 할 때,
curNode의 adjList를 꺼내어 탐색한다. 이 때 adjList 내부의 노드들은 curNode로 부터 이동해온 것 이므로 curNode가 adjList의 노드의 부모가 된다.
따라서 adjList의 노드의 parent에 curNode의 id를 넣고 Queue 탐색을 계속 한다.

해당 과정 진행 후 nodeList의 parent를 출력하면 각각의 부모 노드가 들어있다.

💬 소스코드

 package boj.트리;

import java.io.*;
import java.util.*;

public class Main_BOJ_11725_S2_트리의부모찾기 {
    static Node[] nodeList;
    static class Node {
        int id;
        int parent;
        ArrayList<Node> adjList;
        public Node(int id) {
        	this.id = id;
        	this.adjList = new ArrayList<>();
        }
    }
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        nodeList= new Node[N+1];
        StringTokenizer st;

        for(int i = 1 ; i <= N ; i ++){
            nodeList[i] = new Node(i);
        }

        for(int i = 0 ; i < N-1 ; i ++){
            //연결된 두 정점	
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            //양방향 연결
            nodeList[v1].adjList.add(nodeList[v2]);
            nodeList[v2].adjList.add(nodeList[v1]);
        }

        bfs();

        // 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
        for(int i = 2 ; i <= N ; i++){
            System.out.println(nodeList[i].parent);
        }
    }

    static void bfs(){
        Queue<Node> q = new LinkedList<>();
        boolean[] visited = new boolean[N+1];

        //1번노드가 루트노드
        q.add(nodeList[1]); //루트노드에서 부터 탐색한다.
        visited[nodeList[1].id] = true;

        while(!q.isEmpty()){
            Node curNode = q.poll();

            for(Node nextNode : curNode.adjList){ 	//curNode의 인접노드들 탐색
                if(visited[nextNode.id]) continue;
                visited[nextNode.id] = true;
                nextNode.parent = curNode.id; //나의 부모를 저장한다. (내가 curNode로부터 왔기 때문)
                q.add(nextNode);
            }
        }
    }
}

💯 채점 결과

81176 / 2376