트리의 부모 찾기

• 오랜만에 백준 문제.. 머리가 잘 안돌아가서 쉬운 문제를 풀어봤음.

백준 11725번 : 트리의 부모 찾기

• 트리는 인접 행렬과 인접 리스트를 통해 구현할 수 있는데, 문제에서 N의 개수가 최대 10만이다. 인접 행렬로 구현하면 10만 x 10만 = 총 100만의 공간을 차지하게 되므로 메모리가 4바이트라고 할 때 40기가의 메모리를 필요로 하므로 현재 문제에서는 인접 행렬 방식은 구현할 수 없음.

• 인접 리스트를 구성해서 간 간선을 읽어 두 노드 사이의 연결을 인접 리스트에 추가한다.

• DFS 방식을 이용해서 현재 노드의 부모 노드를 찾고, 그 노드의 값을 저장한 배열의 값을 2부터 출력.

package Silver_2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class find_tree_parents {

    private static ArrayList<Integer>[] adjList;
    private static int[] parents;
    private static boolean [] visited;

    static int N;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        N = Integer.parseInt(br.readLine());
        parents = new int[N+1];
        visited = new boolean[N+1];
        adjList = new ArrayList[N+1];

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

        for(int i = 0; i<N-1; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            adjList[v1].add(v2);
            adjList[v2].add(v1);


        }

        dfs(1);



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



    }

    private static void dfs(int v) {
        visited[v] = true;

        for(int vertex : adjList[v]){
            if(!visited[vertex]){
                parents[vertex] = v;
                dfs(vertex);
            }
        }

    }
}
/*
*
* 1 = true
* 1넘어가고 2
* parent[2] = 1 -> 2의 부모는 1
* dfs(2) */

• 거의 2주만에 문제 푸니깐 알손실 왔다.. 바빠도 꾸준히 하자 ㅜㅜ