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

8월 17일(목) - 트리 (11725번)

11725번: 트리의 부모 찾기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. dfs, bfs 방식의 풀이 아직 모두 구현 어려움

풀이참고 -> https://hongku.tistory.com/253

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(dfs 풀이)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer>[] list = new ArrayList[N+1];
        for(int i=1; i<=N; i++)
        {
            list[i] = new ArrayList<Integer>();
        }

        for(int i=0; i<N-1; i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

        int[] parents = new int[N+1];
        dfs(list, parents, N, 1, 0);

        for(int j=2; j<=N; j++)
        {
            System.out.println(parents[j]);
        }

    }

    public static void dfs(ArrayList<Integer>[] list, int[] parents, int n, int start, int parent){
        parents[start] = parent;
        for(int item : list[start])
        {
            if (item != parent)
            {
                dfs(list, parents, n, item, start);
            }
        }
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(bfs 풀이)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

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

        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());
            list.get(a).add(b);
            list.get(b).add(a);
        }

        int start = 1;
        bfs(start, list, parents, N);

        for(int i=2; i< parents.length; i++)
        {
            System.out.println(parents[i]);
        }

    }

    public static void bfs(int start, ArrayList<ArrayList<Integer>>list, int[] parents, int N){
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        parents[start] = 1;

        while ( !queue.isEmpty())
        {
            int parent = queue.poll();

            for(int item : list.get(parent))
            {
                if(parents[item] == 0)
                {
                    parents[item] = parent;
                    queue.offer(item);
                }
            }
        }

    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ