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

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이

1. 트리는 그래프도 되기 때문에 인접 리스트를 활용하여 DFS로 구현 
2. 먼저 DFS로 구현하였을 때 탐색 순서가 1 → 6 → 3 → 5 → 4 → 2 → 7 로 출력되는 것을 확인
3. 그렇다면 자식 노드로 가기 전에 현재 노드가 다음에 탐색할 노드의 부모 노드이므로 정답 배열에 저장 후 출력 

부족한 부분

해당 문제를 보고 DFS와 유사하게 풀면 되지 않을까 라는 생각으로 풀어서 운이 좋게 정답을 맞추긴 했지만,

시간 복잡도를 고려하여 알고리즘을 선택하진 못 했다.

 

이 부분과 관련한 피드백은 댓글 부탁드립니다 :)

 

추가) 해당 문제에서 방문했던 곳을 다시 가지 않고, 인접리스트로 구현하였기 때문에 O(V+E)의 시간 복잡도를 가지게 된다. ☞ 100,000 + 99,999 = 199,999

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

public class Main {
    // 인접 리스트
    static ArrayList<Integer>[] A;
    // 방문 배열
    static boolean[] visited;
    // 정답 배열
    static int[] answer;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 노드의 개수
        int N = Integer.parseInt(br.readLine());

        // 인접 리스트 초기화 - index를 1부터 사용하기 위해 N+1
        A = new ArrayList[N+1];
        for(int i=1; i<N+1; i++) {
            A[i] = new ArrayList<>();
        }

        // 방문 배열 선언
        visited = new boolean[N+1];

        // 정답 배열 선언
        answer = new int[N+1];

        // 인접 리스트 데이터 삽입
        for(int i=0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            A[s].add(e);
            A[e].add(s);
        }

        // 방문 처리
        for(int i=1; i<N+1; i++) {
            // 방문하지 않았다면
            if(!visited[i]) {
                DFS(i);
            }
        }

        // 정답 배열 출력
        for(int i=2; i<=N; i++) {
            System.out.println(answer[i]);
        }

    }

    private static void DFS(int n) {
        if(visited[n]) return;
        visited[n] = true;
        // 탐색 경로 확인
        //System.out.println(n);
        for(int i : A[n]) {
            if(!visited[i]) {
                // 자식 노드로 가기 직전에 현재 노드가 다음에 탐색할 노드의 부모 노드
                answer[i] = n;
                DFS(i);
            }
        }
    }
}