[JAVA]22856 트리 순회 (골드 4)

 📚 문제  

https://www.acmicpc.net/problem/22856

22856번: 트리 순회

🔍 아이디어  

만약 현재 노드가 유사 중위 순회의 끝이라면 유사 순위를 종료한다는 부분을 잘못 이해해서 여러 번 틀렸던 문제였습니다. 이 구문은 현재 노드가 중위 순회가 끝났다면 다시 올라가지 않아도 된다는 것을 의미합니다. 즉 왼쪽으로 가는 경우는 반드시 루트로 다시 올라와야 하지만 오른쪽의 경우는 중위순회가 끝난 상태라면 다시 올라오지 않아도 됩니다. (중위 순회 : 왼쪽 자식 -> root -> 오른쪽 자식) 

 

따라서 왼쪽 자식을 가는 경우는 내려갔다 올라오는 점수를 모두 세 주었지만

오른쪽 자식으로 가는경우는 모든 노드를 방문한 상태라면 다시 올라오지 않고 종료하도록 하였습니다.

 

📝 풀이 

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

public class Boj_22856_트리순회 {
    private static class Node {
        int root;
        Node left;
        Node right;

        public Node(int root) {
            this.root = root;
        }

        public void set(Node left, Node right) {
            this.left = left;
            this.right = right;
        }
    }

    private static int visitedCnt = 0;
    private static boolean[] visited;
    private static int n;

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

        n = Integer.parseInt(br.readLine());
        Node[] nodes = new Node[n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i);
        }
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int left = Integer.parseInt(st.nextToken()) - 1;
            int right = Integer.parseInt(st.nextToken()) - 1;

            if (left != -2 && right != -2) {
                nodes[a].set(nodes[left], nodes[right]); //자식이 없는경우
            } else if (left != -2) {
                nodes[a].set(nodes[left], null); //왼쪽 자식만 있는 경우
            } else if (right != -2) {
                nodes[a].set(null, nodes[right]); //오른쪽 자식만 있는 경우
            }
        }
        System.out.println(dfs(nodes[0]));
    }

    private static int dfs(Node now) {
        //왼쪽만 있으면 다시 올라가야 하고
        //오른쪽에서 중위 순회가 끝났으면 올라가지 않아도 됨
        int score = 0;

        if (now.left != null && !visited[now.left.root]) {
            score++; //내려가는 비용
            score += dfs(now.left);
            score++; //다시 올라가는 비용
        }

        //중위 순회함을 체크한다.
        visited[now.root] = true;
        visitedCnt++;

        if (now.right != null && !visited[now.right.root]) {
            score++; //내려가는 비용
            score += dfs(now.right);
            if (visitedCnt == n) { //오른쪽에서 중위 순회가 종료되었다.다시 올라가지 않아도 된다.
                return score;
            }
            score++;
        }

        return score;

    }
}