[백준/JAVA] 11725번: 트리의 부모 찾기

🔺 문제

11725번: 트리의 부모 찾기

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static ArrayList<Integer> tree[];   // 인접 리스트
    static boolean visited[];           // 방문 배열
    static int answer[];                // 부모 노드 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        visited = new boolean[N + 1];
        answer = new int[N + 1];
        
        // 인접 리스트 초기화
        tree = new ArrayList[N + 1];
        for(int i = 0 ; i < tree.length ; i++) {
            tree[i] = new ArrayList<>();
        }
        
        // 양방향 인접 리스트 채우기
        for(int i = 1 ; i < N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            tree[a].add(b);
            tree[b].add(a);
        }
        
        DFS(1); // 부모 노드부터 DFS 시작
        
        StringBuilder sb = new StringBuilder();
        for(int i = 2 ; i <= N ; i++) {
            sb.append(answer[i] + "\n");
        }
    }
    
    public static void DFS(int num) {
        visited[num] = true;
        
        for(int i : tree[num]) {
            if(!visited[i]) {
                answer[i] = num;    // ⭐ DFS 탐색하면서 부모 노드를 정답 배열에 저장
                DFS(i);
            }
        }
    }    
}

✅ 해결 아이디어
✔ DFS /  BFS
- DFS 탐색하면서 부모 노드를 정답 배열에 저장 (45번째 줄 : answer[i] = num)

 

---

🔺 다른 풀이들

- BFS 활용한 방법도 확인

[백준] 11725 : 트리의 부모 찾기 - Java

백준/11725번 :: 트리의 부모찾기 (java 자바) - DFS, BFS 이용

---

💬 느낀 점

트리는 그래프 구현 방식을 이용할 수 있고,

탐색 역시 그래프 알고리즘을 사용할 수 있다! 는 점을 잊지 말자

 

 

1회독	2회독	3회독	4회독	5회독
V	230628	240103	240616

 

(+ 230628 2회독)

BFS 를 썼다.

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
 
    static ArrayList<Integer>[] tree;
    static boolean[] visited;
 
    static int[] parent;    // 📍 부모 노드 배열 📍
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        tree = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            tree[i] = new ArrayList<>();
        }
        visited = new boolean[N + 1];
        parent = new int[N + 1];
        
        for(int i = 1 ; i <= N - 1 ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            tree[s].add(e);
            tree[e].add(s);
        }
        
        bfs(1);
        
        // 2번 노드부터 부모 노드 출력하기
        for(int i = 2 ; i <= N ; i++) {
            sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
    }
    
    private static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        
        visited[num] = true;
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int next : tree[now]) {
                if(!visited[next]) {
                    visited[next] = true;
                    parent[next] = now;   // 🔔 탐색하면서 부모 노드를 정답 배열에 저장! 🔔
                    queue.add(next);
                }
            }
        }
    }
}
 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편