[백준] 22856 트리 순회 java 풀이

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/22856

(1) 조건 분석 📊

1. 중위 순회로 나오는 마지막 노드를, 문제에서 주어진 조건인 '유사 중위 순회' 방식으로 노드를 순회 했을 때, 몇 번의 이동만에 중위 순회 상 마지막 노드에 도달할 수 있는지 이동 횟수를 구해라
2. 여기서 이동이란 하나아ㅢ 노드에서 다른 노드로 한 번 움직이는 행위이다.

2. 코드가 나오기까지 🛠️

KEY WORD: DFS

1. 중위 순회 마지막 노드 구하기
2. 유사 중위 순회 구현해서 마지막 노드까지의 방문 횟수 구하기

(1) 시간복잡도 분석 ⏳

최대 노드 개수가 $100,000$ 개 인데, DFS는 $O(V + E)$ 임으로, $200,000$ 개를 안 넘는다.

3. 코드 🌐

import java.io.*;  
import java.util.*;  


public class Main {  
    static int N, last_one, cnt;  
    static int answer = 0;  
    static ArrayList<Integer> [] lists;  
    static boolean [] check;  
    public static void main(String[] args) throws IOException {  
        init();  
        inorder_traversal(1);  
        similar_inorder(1);  
        System.out.printf("%d", answer);  
    }  

    public static void inorder_traversal(int now) {  
        if(lists[now].get(0) != -1) inorder_traversal(lists[now].get(0));  
        last_one = now;  
        if(lists[now].get(1) != -1) inorder_traversal(lists[now].get(1));  
    }  

    public static void similar_inorder(int now) {  
        if(lists[now].get(0) != -1 && !check[lists[now].get(0)]) {  
            cnt++;  
            similar_inorder(lists[now].get(0));  
            cnt++;  
        }  
        if(lists[now].get(1) != -1 && !check[lists[now].get(1)]) {  
            cnt++;  
            similar_inorder(lists[now].get(1));  
            cnt++;  
        }  
        if(now == last_one) {  
            answer = cnt;  
            return;  
        } else check[now] = true;  
    }  


    public static void init() throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        N = Integer.parseInt(br.readLine());  
        lists = new ArrayList[N+1];  
        check = new boolean[N+1];  

        for(int i = 1; i <= N; i++){  
            lists[i] = new ArrayList<>();  
        }  

        for(int i = 0; i < N; i++){  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            int me = Integer.parseInt(st.nextToken());  
            int left = Integer.parseInt(st.nextToken());  
            int right = Integer.parseInt(st.nextToken());  
            lists[me].add(left);  
            lists[me].add(right);  
        }  
    }}

4. 트러블 슈팅 or 배운 점📝

다른 사람의 풀이를 보니, 수학적 사고를 해서 풀면, 시간을 더 단축할 수 있었다.

중위 순회는 언제나 오른쪽 제일 끝에 있는 노드를 고른다.

온전한 DFS를 거친다고 치면은 이동 횟수 = 간선의 개수 x 2* 이다.

여기서 맨 마직 노드의 깊이만큼 빼주기만 하면 답이 된다.

즉 간선의 개수 x 2 - 루트 노드부터 중위 순회 마지막 조회 노드까지의 깊이

import java.io.*;  
import java.util.*;  

public class Main {  
    static int N;  
    static ArrayList<Integer>[] lists;  
    static int lastNode; // 중위순회 마지막 노드 번호  
    static int lastDepth; // 마지막 노드까지의 depth  
    public static void main(String[] args) throws IOException {  
        init();  
        findLastNode(1);          // 1. 중위순회로 마지막 노드 찾기  
        findDepth(1, 0);          // 2. 마지막 노드까지의 depth 탐색  

        int edgeCount = N - 1;    // 3. 전체 간선 개수  
        int answer = edgeCount * 2 - lastDepth;  
        System.out.println(answer);  
    }  

    // 중위순회로 마지막 노드 발견  
    static void findLastNode(int now) {  
        if (lists[now].get(0) != -1) findLastNode(lists[now].get(0));  
        lastNode = now;  
        if (lists[now].get(1) != -1) findLastNode(lists[now].get(1));  
    }  

    // DFS로 lastNode까지의 거리(depth) 측정  
    static void findDepth(int now, int depth) {  
        if (now == -1) return;  
        if (now == lastNode) lastDepth = depth;  
        if (lists[now].get(0) != -1) findDepth(lists[now].get(0), depth + 1);  
        if (lists[now].get(1) != -1) findDepth(lists[now].get(1), depth + 1);  
    }  

    public static void init() throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        N = Integer.parseInt(br.readLine());  
        lists = new ArrayList[N+1];  

        for(int i = 1; i <= N; i++)  
            lists[i] = new ArrayList<>();  
        for(int i = 0; i < N; i++){  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            int me = Integer.parseInt(st.nextToken());  
            int left = Integer.parseInt(st.nextToken());  
            int right = Integer.parseInt(st.nextToken());  
            lists[me].add(left);  
            lists[me].add(right);  
        }  
    }
}