[JAVA]BOJ 11725, 트리의 부모 찾기

트리를 활용한 간단한 문제이다.

트리에 대해 짧게 요약하고 넘어가자면 ..

트리 : 순환이 없는 그래프
트리종류 : 일반트리 이진트리 N-진트리 균형트리 힙.. 등이 있음
순회방법 : preorder, inorder, postorder, levelorer 등이 있음
dfs, bfs : 그래프와 트리에 사용할 수 있는 탐색 알고리즘
         - dfs : preorder, inorder, postorder 방식으로 탐색 가능
         - bfs : leveloder와 같음

자바에서 트리를 구현할때는 리스트를 이용한다.

 

1. 리스트를 이용해 빈 노드를 가진 트리를 만든다.

2. 노드에 간선을 추가한다.

3. DFS 탐색(preorder)으로 부모를 찾는다.

4. 부모를 출력한다.

 

1. 메인 -> 2. 노드에 간선 추가와 3. DFS탐색은 함수로 따로 뺐다. 

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, i;
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        List<List<Integer>> graph = new ArrayList<>();
        int[] parentArr = new int[N + 1];
        int[] visited = new int[N + 1];

        // 그래프에 노드 추가 -> 0번은 사용하지 않음
        for(i=0;i<=N;i++)
            graph.add(new ArrayList<>());

        // 노드에 간선 추가
        for(i=0;i<N-1;i++){
            st = new StringTokenizer(br.readLine());
            addEdge(graph, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // DFS -> preoder 로 부모 탐색
        DFS(parentArr, visited, graph, 1);

        // 0번째 노드와 루트는 제외하고 출력
        for(i=2;i<=N;i++)
            System.out.println(parentArr[i]);
    }
}

 

2. addEdge함수 -> 노드에 간선 추가

public static void addEdge(List<List<Integer>> graph, int u, int v) {
    // 무방향 그래프이므로 양방향 추가
    graph.get(u).add(v);
    graph.get(v).add(u);
}

방향이 없는 그래프이므로 간선을 추가한다. GPT가 설명을 잘 해줘서 캡쳐로 설명추가

 

3. DFS함수 -> preoder방식

public static void DFS(int[] parentArr, int[] visited, List<List<Integer>> graph, int node){
    // preoder 방식
    visited[node] = 1;

    for(int neighbor : graph.get(node)){ // node와 인접한 노드(neighbor) 탐색하기
        if(visited[neighbor] == 0){ // 탐색되지 않았다면
            parentArr[neighbor] = node; // neighbor는 node의 자식임
            DFS(parentArr, visited, graph, neighbor); // neighbor를 node로해서 재귀 탐색
        }
    }
}

우선, node(노드번호)가 들어왔을때 탐색했다고 저장한다(visited[node] = 1). 그리고 node와 인접한 노드들이 탐색이 되었는지 확인한다. 인접한 노드를 neighbor라고 한다. neighbor가 탐색이 되지 않았다면, node는 neighbor의 부모이다. 그래서 parentArr[neighbor] = node라고 부모를 저장해준다. 

 

위의 GPT가 든 예시로 설명하면

node = 1이고, 인접한 노드(neighbor = graph.get(node)))는 [2, 3] 이므로 처음에는 2, 두 번째는 3이 될것이다. 노드1(현재 node = 1이므로)은 탐색되었다고 표시하고 인접한 노드 중, 첫번째인 2를 neighbor로 지정한다. neighbor(노드2)는 아직 탐색되지 않았으므로 if문을 실행하게된다. 그리고 node(노드1)을 neighbor(노드2)의 부모라고 저장하고 neighbor(노드2)를 node로 정해서 DFS탐색(재귀)를 실행한다.

 

node = 2이고, 인접한 노드는 [1], 노드1만 있다. 그리고 node(노드2)는 탐색되었다고 저장한다.(visited[2] = 1) node(노드2)에 대한 새로운 neighbor를 정한다. 인접한 노드는 노드1 뿐이므로 neighbor = 1이 될 것이다. neighbor(노드1)은 이전에 탐색되었으므로(visited[1] = 1) if문을 실행하지 않고 끝낸다.

 

끝났으므로 다시 node = 1로 돌아온다. 그리고 neighbor = 3(노드3)이 된다. 똑같은 과정을 반복하고 노드3의 부모는 노드1로 저장되고 끝날것이다.

 

이 코드는 .. 나와 인접한 노드가 이미 방문된 적이 있다면, 내 부모임을 뜻한다. 그리고 나와 인접한 노드가 방문되지 않았다면 내 자식임을 뜻한다. preoder가 노드를 방문하고 좌, 우를 방문하는 방식이기 때문이다. inorder나 postorder로 코드를 짜면 방문한 순서가 달라질 것이다. 

 

트리를 활용한 첫 번째 문제였는데, 개념을 알아서 어렵지않게 풀 수 있었다. C의 구조체로 트리를 직접 만들고 다양한 탐색을 해 본 적은 있지만, java의 list로 만드는건 처음이었다. 그리고 훨씬 편리하다는걸 느꼈다.

---

아래는 전체 코드이다.

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 BOJ11725 {
    public static void addEdge(List<List<Integer>> graph, int u, int v) {
        // 무방향 그래프이므로 양방향 추가
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    public static void DFS(int[] parentArr, int[] visited, List<List<Integer>> graph, int node){
        // preoder 방식
        visited[node] = 1;

        for(int neighbor : graph.get(node)){ // node와 인접한 노드(neighbor) 탐색하기
            if(visited[neighbor] == 0){ // 탐색되지 않았다면
                parentArr[neighbor] = node; // neighbor는 node의 자식임
                DFS(parentArr, visited, graph, neighbor); // neighbor를 node로해서 재귀 탐색
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, i;
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        List<List<Integer>> graph = new ArrayList<>();
        int[] parentArr = new int[N + 1];
        int[] visited = new int[N + 1];

        // 그래프에 노드 추가 -> 0번은 사용하지 않음
        for(i=0;i<=N;i++)
            graph.add(new ArrayList<>());

        // 노드에 간선 추가
        for(i=0;i<N-1;i++){
            st = new StringTokenizer(br.readLine());
            addEdge(graph, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // DFS -> preoder 로 부모 탐색
        DFS(parentArr, visited, graph, 1);

        // 0번째 노드와 루트는 제외하고 출력
        for(i=2;i<=N;i++)
            System.out.println(parentArr[i]);
    }
}