백준 11725 트리의 부모 찾기(DFS)

 

문제 해석

- 주어진 숫자들을 그래프로 연결했을 때에, 각 숫자마다 부모가 누구인지를 구하는 문제이다.
처음에는 설명만 읽고나서 뭔소리인가 문제 해석에 시간이 좀 걸렸다. 

- 루트는 무조건 1부터 시작한다. 

헷갈렸던 점

- 그래프를 어떻게 구성해야 하는가가 헷갈렸다. 배열로 풀려고 했으나, 인덱스가 늘어나면서 처리해주기 까다로워 리스트가 적당했다. 이 문제를 통해서 다시 한번 복습할 수 있는 계기가 되었다.

- dfs를 어떻게 구성해야 할지 쉬울듯 안쉬울듯 자꾸 머리가 안굴러가서 애먹었다. 직접 메모장에 단계 별로 변수를 적어보면서 구성했다. 

- 다음 노드에서 이전 parent 노드로 다시 돌아가면 무한루프에 빠지게 되는데, 이 부분을 어떻게 처리해야 할지 고민을 좀 했다.

그래서 num != parent 일 때에 조건으로 만들어주었다.

if(num != parent)

- 위에서 말한 dfs 설계 시 오래 걸렸던 부분이다.

어떻게 설계해야 하나 dfs(num, parent), dfs(num) 등의 생각들이 들었었고,
int num = array.get(node).get(i); 부분과 유기적으로 굴러가야 하는데, 내 머리가 굴러가지가 않았다.

dfs(num, node);

- 다 푼 것 같았는데, 부모 노드가 꼬이는 현상이 있었다. 이유는 array.get(node).size() 만큼 돌면서 계속해서 부모 노드를 갱신해주고 있었어서, 한번만 갱신하도록 처리하였다. 

if(parentInfo[num] == 0)
	parentInfo[num] = node;

전체 코드

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 Main {
    public static void main(String[] args) throws IOException {
        solution();
    }
    static class Tree{
        int data;
        int left;
        int right;
    }
    static Tree[] trees;
    static int[] parentInfo;
    static List<List<Integer>> array;
    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        trees = new Tree[N+1];
        parentInfo = new int[N+1];
        array = new ArrayList<>();

        // 그래프 초기화
        for (int i = 0; i < N+1; i++) {
            List<Integer> arr = new ArrayList<>();
            array.add(arr);
        }

        // 그래프 구성
        for(int i=0; i<N-1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            array.get(node1).add(node2);
            array.get(node2).add(node1);
        }

        // DFS 시작
        dfs(1, 1);
        // 출력
        for(int i=2; i<parentInfo.length; i++){
            System.out.println(parentInfo[i]);
        }
    }
    public static void dfs(int node, int parent){
        for (int i = 0; i < array.get(node).size(); i++) {
            // 그래프에 연결된 노드들을 가져옴
            int num = array.get(node).get(i);
            // 부모 노드가 갱신되지 않도록 처리
            if(parentInfo[num] == 0)
                parentInfo[num] = node;
            // 부모 노드가 아닌 경로만 탐색
            if(num != parent) {
                dfs(num, node);
            }
        }
    }
}