[11725] 트리의 부모 찾기

✔ 트리의 부모 찾기

[백준 11725]

문제 분석하기

주어지는 데이터가 단순하게 연결돼 있는 두 노드를 알려 주는 것이므로 데이터를 저장할 때 양방향 엣지로 간주하고 저장한 후

트리의 루트인 1번 노드부터 DFS로 탐색하면서 부모 노드를 찾아 주는 것으로 문제에 접근

손으로 풀어보기

1. 인접 리스트로 트리 데이터를 구현
2. DFS 탐색을 수행
   • 수행할 때는 부모 노드의 값을 정답 배열에 저장
3. 정답 배열의 2번 인덱스부터 값을 차례대로 출력

슈도코드 작성하기

N(노드 개수)
tree(트리 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열)
answer(부모 노드 저장 정답 배열)
for(N의 개수만큼 반복하기) {
    tree 인접 리스트의 각 ArrayList 초기화하기
}
for(N - 1개의 개수만큼 반복하기) {
    tree 인접 리스트에 트리 데이터 저장하기
}
1번 노드부터 DFS 실행하기
for(2 ~ N 반복하기) {
    answer 배열 출력하기
}

DFS {
    visited 배열에 현재 노드 방문 기록하기
    if(현재 노드의 연결 노드 중 방문하지 않은 노드) {
        부모 노드 저장하기
        DFS 실행하기(재귀 함수 형태)
    }
}

코드 구현하기

/**
 * 11725) 트리의_부모_찾기
 */
public class D067_11725 {
    static boolean[] visited;
    static ArrayList<Integer> tree[];
    static int answer[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(노드 개수)
        int N = sc.nextInt();
        // visited(방문 기록 저장 배열)
        visited = new boolean[N + 1];
        // tree(트리 데이터 저장 인접 리스트)
        tree = new ArrayList[N + 1];
        // answer(부모 노드 저장 정답 배열)
        answer = new int[N + 1];
        // tree 인접 리스트의 각 ArrayList 초기화하기
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }
        // tree 인접 리스트에 트리 데이터 저장하기
        for (int i = 1; i < N; i++) {
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            tree[n1].add(n2);
            tree[n2].add(n1);
        }
        // 1번 노드(부모 노드)부터 DFS 실행하기
        DFS(1);
        // answer 배열 출력하기
        for (int i = 2; i <= N; i++) {
            System.out.println(answer[i]);
        }

    }

    // DFS
    public static void DFS(int number) {
        // visited 배열에 현재 노드 방문 기록하기
        visited[number] = true;
        // 현재 노드의 연결 노드 중 방문하지 않은 노드
        for (int i : tree[number]) {
            if (!visited[i]) {
                // 부모 노드 저장하기
                answer[i] = number;
                // DFS 실행하기(재귀 함수 형태)
                DFS(i);
            }
        }
    }
}