[코딩 테스트 - Java] 백준11725 - 트리의 부모 찾기

김수빈·2022년 11월 3일
0

코딩테스트

목록 보기
12/16

트리의 부모 찾기 (DFS/BFS)

INPUT

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

OUPUT

2번 노드부터 각 노드의 부모를 줄 단위로 출력

LOGIC

1번 노드는 항상 루트 노드 이므로, 인풋으로 들어온 연결들을 1번 루트노드 부터 탐색한다.
탐색하면서 아래로 내려갈 때(자식 노드로 향할 때) 자식 노드의 부모 노드를 저장한다.

ex) 1번 에서 2번 노드로 갈 땐 2번 노드의 부모가 1번이 됨

package 백준;

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

public class baek11725 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] answer = new int[n+1];

        // [[0번 노드와 연결된 애들], [1번 노드와 연결된 애들], [2번 노드와 연결된 애들], ... [n번 노드와 연결된 애들] ]
        ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
        boolean[] visited = new boolean[n+1]; // 0부터 n 까지 방문
        for(int i=0;i<n+1;i++){
            arrayList.add(new ArrayList<Integer>());
        }
        for(int i=0;i<n-1;i++){
            String[] info = br.readLine().split(" ");
            int start = Integer.parseInt(info[0]);
            int end = Integer.parseInt(info[1]);
            arrayList.get(start).add(end);
            arrayList.get(end).add(start);
        }
        
        visited[1]=true;
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(1);
        while(!queue.isEmpty()){
            int num = queue.poll();
            ArrayList<Integer> connections = arrayList.get(num);
            for(int connection : connections){
                if(!visited[connection]){
                    visited[connection]=true;
                    answer[connection]=num;
                    queue.add(connection);
                }
            }
        }



        StringBuilder sb = new StringBuilder();
        for(int i=2;i<answer.length;i++){
            sb.append(answer[i]).append("\n");
        }
        System.out.println(sb);

    }
}

회고

처음 풀 땐, ArrayList<ArrayList> 가 아닌 ArrayList<int[]> 로 풀려 했다.

전자는 해당 인덱스의 노드가 연결된 노드들의 정보를 담는 형태이고, 후자는 모든 연결 내용을 포함한 형태이다.

근데 시간 초과가 계속 났는데, 후자는 현재 노드의 자식 노드를 탐색할 때 마다 매번 탐색을 했기에 시간복잡도가 높았던 것이였다.

그래서 현재 위치한 노드와 연결된 애들만 볼 수 있는 전자의 방법으로 바꾸었더니 통과했다.

참고로 인풋의 노드의 갯수가 10만개 까지 나오므로, 직접 for 문을 돌며 print하는게 아닌 StringBuilder 를 이용하면 시간이 줄어든다.

0개의 댓글