알고리즘 풀이 - 백준 11725(트리의 부모 찾기, 트리/그래프(BFS, DFS))

 

관련글

 

트리 관련 포스팅은 여기를 참조
그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

루트 없는 트리의 구조가 주어졌고 1이 루트라고 지정되었을 때, 각 노드의 부모를 구하는 프로그램 작성하기

 

 

2. 풀이

 

이 문제는 단순히 트리를 그래프 형태로 구현한 뒤, BFS / DFS를 통해 탐색을 수행하며 각각의 노드의 부모 노드를 지정하여 그 결과를 출력하는 문제이다.

코드를 통해 간단히 이해할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

① BFS로 풀기

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

public class Main{
    static int n;
    static int[] parent;
    static boolean[] visited;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // ******************** 주어진 값 저장 *********************
        n = Integer.parseInt(st.nextToken());
        ArrayList<Integer>[] graph = new ArrayList[n+1];
        for(int i=1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        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());
            
            // 그래프 형태로 트리 저장
            graph[u].add(v);
            graph[v].add(u);
        }
        // ***************** 주어진 값 저장 완료 ********************
        
        
        // ***************** BFS를 통해 트리 순회하여 부모 찾기 ***************
        parent = new int[n+1];
        visited = new boolean[n+1];
        Queue<Integer> q = new LinkedList<>();
        
        q.offer(1);
        visited[1] = true;
        while(!q.isEmpty()){
            int u = q.poll();
            for(int v : graph[u]){
                if(!visited[v]){
                
                    // 아직 미방문한 각 노드를 다음 탐색 대상으로 넣고
                    // 각 노드의 부모를 현재 노드로 지정
                    q.offer(v);
                    visited[v] = true;
                    parent[v] = u;
                }
            }
        }
        // ******************** 부모 찾기 완료 ********************************
        
        StringBuilder sb = new StringBuilder();
        for(int i=2; i <= n; i++){
            sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
        br.close();
    }
}

 

② DFS로 풀기

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

public class Main{
    static int n;
    static int[] parent;
    static boolean[] visited;
    static ArrayList<Integer>[] graph;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        graph = new ArrayList[n+1];
        for(int i=1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        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());
            
            graph[u].add(v);
            graph[v].add(u);
        }
        
        parent = new int[n+1];
        visited = new boolean[n+1];
        dfs(1);
        
        StringBuilder sb = new StringBuilder();
        for(int i=2; i <= n; i++){
            sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
        br.close();
    }
    
    private static void dfs(int u){
        for(int v : graph[u]){
            if(!visited[v]){
                parent[v] = u;
                visited[v] = true;
                dfs(v);
            }
        }
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.