백준 온라인 저지 - 11725번: 트리의 부모 찾기

🔍 문제

---

11725번: 트리의 부모 찾기

 

✏️ 풀이 - Java

---

풀이를 찾아보니 bfs로 찾아본 사람이 더 많은 것 같았지만 그냥 dfs로 풀었다.
트리를 루트부터 타고 내려가면서 만약 자신과 연결된 노드가 이미 방문한적이 있다면, 부모로 보고 parent 배열에 넣어주었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] parent;
    static boolean[] visit;
    static ArrayList<ArrayList<Integer>>list;

    public static void main(String[] args) throws NumberFormatException, IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         StringTokenizer st;

         N = Integer.parseInt(br.readLine());
         parent = new int[N+1];
         visit = new boolean[N+1];
         list = new ArrayList<>();

         for(int i = 0; i <= N; i++) {
             list.add(new ArrayList<Integer>());
         }

         for(int i = 1; i < N; i++) {
             st = new StringTokenizer(br.readLine());

             int idx1 = Integer.parseInt(st.nextToken());
             int idx2 = Integer.parseInt(st.nextToken());

             list.get(idx1).add(idx2);
             list.get(idx2).add(idx1);
         }

         dfs(1);

         for(int i = 2; i < N+1; i++) {
             bw.write(parent[i] + "\n");
         }

         bw.flush();
         bw.close();
         br.close();

    }

    static void dfs(int node) {

        if(!visit[node]) {
            visit[node] = true;

            for(int n : list.get(node)) {
                if(visit[n]) parent[node] = n;
                dfs(n);
            }
        }
    }
}