백준_Java_22856_트리순회

문제

백준 22856번 - 트리 순회

유사 중위 순회를 수행하면서 이동한 횟수를 계산하는 문제입니다.
유사 중위 순회는 다음 규칙을 따릅니다:

1. 현재 노드의 왼쪽 자식 노드가 존재하고 방문하지 않았다면, 왼쪽 자식으로 이동합니다.
2. 그렇지 않고 오른쪽 자식 노드가 존재하고 방문하지 않았다면, 오른쪽 자식으로 이동합니다.
3. 그렇지 않고 현재 노드가 중위 순회의 마지막 노드라면, 탐색을 종료합니다.
4. 그렇지 않다면 부모 노드로 이동합니다.

중위 순회를 따르는 방식으로 이동하며, 이동한 횟수를 출력합니다.

---

풀이

1) 문제풀이

1. 트리를 left와 right 배열로 표현하여, 각 노드의 왼쪽과 오른쪽 자식 정보를 저장합니다.
2. 중위 순회의 마지막 노드를 findLastNode 함수로 찾아냅니다.
   • 마지막 노드는 오른쪽 자식이 없을 때까지 오른쪽으로 내려가며 찾을 수 있습니다.
3. 유사 중위 순회를 수행하며 이동 횟수를 계산합니다.
   • 스택(Stack)을 사용해 부모 노드로 돌아갈 경로를 관리합니다.
   • 방문한 노드는 Set에 기록하여 중복 방문을 방지합니다.

2) 중위 순위의 마지막 노드 찾기

문제를 해결하기 위해 중위 순회의 마지막 노드를 정확히 구하는 과정이 필요합니다.

중위 순회의 정의에 따라 트리의 가장 오른쪽 자식이 마지막 노드가 됩니다.
예를 들어, 주어진 트리가 다음과 같을 때:

    1
   / \
  2   3
     /
    4 

중위 순회는 2 → 1 → 4 → 3의 순서로 진행되며, 마지막 노드는 3입니다.
이를 해결하기 위해 오른쪽 자식을 따라 끝까지 내려가는 방식으로 마지막 노드를 찾습니다.

static int findLastNode(int[] right, int cur) {
    while (right[cur] != -1) {
        cur = right[cur]; // 오른쪽 자식을 따라가며 마지막 노드 탐색
    }
    return cur;
}

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력 받기
        int N = Integer.parseInt(br.readLine());
        int[][] tree = new int[N][3];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            tree[i][0] = Integer.parseInt(st.nextToken());
            tree[i][1] = Integer.parseInt(st.nextToken());
            tree[i][2] = Integer.parseInt(st.nextToken());
        }

        // 결과 출력
        int result = process(tree, N);
        bw.write(result + "\n");

        // 버퍼 닫기
        bw.flush();
        br.close();
        bw.close();
    }

    static int process(int[][] tree, int N) {
        int[] left = new int[100001];
        int[] right = new int[100001];

        // 트리 초기화
        for (int[] node : tree) {
            int n = node[0];
            int l = node[1];
            int r = node[2];

            left[n] = l;
            right[n] = r;
        }

        // 마지막 노드 찾기
        int lastNode = findLastNode(right, 1);

        // 유사 중위 순회
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        int cur = 1; // 루트 노드부터 시작
        int moves = 0;

        while (true) {
            moves++;

            // 방문 처리
            visited.add(cur);

            // 왼쪽 자식으로 이동
            if (left[cur] != -1 && !visited.contains(left[cur])) {
                stack.push(cur);
                cur = left[cur];
                continue;
            }

            // 오른쪽 자식으로 이동
            if (right[cur] != -1 && !visited.contains(right[cur])) {
                stack.push(cur);
                cur = right[cur];
                continue;
            }

            // 마지막 노드 도달 시 종료
            if (cur == lastNode) break;

            // 부모 노드로 복귀
            if (!stack.isEmpty()) {
                cur = stack.pop();
            }
        }

        return moves - 1; // 마지막 이동 제외
    }

    static int findLastNode(int[] right, int cur) {
        while (right[cur] != -1) {
            cur = right[cur];
        }
        return cur;
    }
}