[자바] 백준 22856: 트리 순회

 

1. 문제

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

1

2

3

 

2. 문제 접근법

2-1. 중위 순회란?

• 중위 순회는 왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 순서대로 방문한다.
• 따라서 그림 1의 그래프가 존재할 때, 중위 순회 결과는 D -> B -> F -> E -> G -> A -> C이다.

그림1

 

• 그림 2의 중위 순회 결과 : 4 -> 2 -> 5 -> 1 -> 6 -> 7 -> 3

그림2

2-2. 중위 순회에서 마지막으로 방문할 노드 찾기

• 그림 1의 마지막 노드 : C
• 그림 2의 마지막 노드 : 3

 

중위 순회 시에 마지막으로 방문할 노드를 구하는 자바 코드이다. 

• v : 현재 노드(부모 노드)
• nodes.get(v).get(0) : 왼쪽 자식 노드
• nodes.get(v).get(1) : 오른쪽 자식 노드

아래 코드에서는 왼쪽 노드를 고려하지 않았다. 중위 순회는 왼쪽 노드 -> 현재 노드 -> 우측 노드 순으로 방문하기 때문에, 왼쪽 노드는 마지막 노드가 될 수 없다. 최소 현재 노드(v)이거나 또는 오른쪽 노드만이 중위 순회의 마지막 노드가 될 수 있다.

static void findLastNode(int v) {
    lastNode = v; // 1. 현재 노드(부모 노드)

    // 2. 오른쪽 자식 노드가 존재하지 않을 때
    if (nodes.get(v).get(1) == -1) {
        return;
    }

    // 3. 오른쪽 자식 노드가 존재할 때
    findLastNode(nodes.get(v).get(1));
}

위 코드를 해석해 보자면,

1. 일단 현재 노드(부모 노드)를 마지막 노드로 설정한다.
2. 오른쪽 노드가 존재하지 않으면 함수를 종료한다.
3. 오른쪽 노드가 존재한다면 재귀 함수를 통해 오른쪽 노드에 연결된 노드들 중에서 마지막 노드를 탐색한다.

위 과정을 통해 아래 그림에서 3번이 마지막 노드가 되는 이유를 알아보자. 

1. findLastNode(1)을 호출한다.
   1. 루트 노드는 반드시 존재하며, 루트 노드는 1이다.
   2. 현재 마지막 노드(lastNode)는 1이다.
2. 오른쪽 노드(3)가 존재하므로 재귀 함수를 호출한다.
   1. 마지막 노드를 3으로 갱신한다.
3. 현재 노드(3)를 기준으로 오른쪽 노드가 존재하지 않는다. 따라서 중위 순회의 마지막 노드는 3이 된다.

그림2

 

2-3. 유사 중위 순회

유사 중위 순회란 중위 순회를 수행하되, 탐색을 수행할 때마다 방문한 노드를 출력한다.

• 중위 순회 탐색 결과 : 4 2 5...
• 유사 중위 순회 탐색 결과 : 1 2 4 2 5 2...

유사 중위 순회를 traverse() 메서드에 구현하였다.

1. 탐색 횟수를 1 증가시킨다. (moveCount)
2. 현재 노드를 방문처리 한다. (visited)
   1. Set 자료구조는 중복 저장을 하지 않는다.
3. 현재 노드와 연결된 자식 노드를 탐색한다.
   1. child 값이 -1이라면 자식 노드가 존재하지 않음을 의미한다.
   2. nodes.get(v)에는 두 개의 값이 저장되어 있는데, 왼쪽 노드와 오른쪽 노드의 정보를 차례대로 저장한다.
   3. 따라서 child에는 왼쪽 노드와 오른쪽 노드가 순서대로 저장되며, child가 -1이라면 해당 방향의 자식 노드가 없다는 것이고, -1이 아니라면 해당 방향의 자식 노드가 존재함을 의미한다.
4. 중위 순회가 종료되었는지 확인한다. 아래 두 가지 조건을 모두 만족해야 한다.
   1. 모든 노드를 탐색해야 한다. -> visited.size() == N
   2. 현재 노드(부모 노드)가 중위 순회의 마지막 노드이어야 한다. -> v == lastNode

public class Main {

    static int N;
    static List<List<Integer>> nodes = new ArrayList<>();
    static int lastNode;
    static Set<Integer> visited = new HashSet<>();
    static int moveCount = -1;
    
    .. 생략

    static void traverse(int v) {
        moveCount++;
        visited.add(v);

        for (int child : nodes.get(v)) {
            if (child != -1) {
                traverse(child);
                moveCount++;
            }
            if (visited.size() == N && v == lastNode) {
                System.out.println(moveCount);
                System.exit(0);
            }
        }
    }

}

 

3. 전체 코드

public class Main {

    static int N;
    static List<List<Integer>> nodes = new ArrayList<>();
    static int lastNode;
    static Set<Integer> visited = new HashSet<>();
    static int moveCount = -1;

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

        N = Integer.parseInt(br.readLine());
        for (int i = 0; i <= N; i++) {
            nodes.add(new ArrayList<>());
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            nodes.get(v).add(left);
            nodes.get(v).add(right);
        }

        findLastNode(1);
        traverse(1);

        System.out.println(moveCount);
    }

    static void findLastNode(int v) {
        lastNode = v; // 1. 현재 노드(부모 노드)

        // 2. 오른쪽 자식 노드가 존재하지 않을 때
        if (nodes.get(v).get(1) == -1) {
            return;
        }

        // 3. 오른쪽 자식 노드가 존재할 때
        findLastNode(nodes.get(v).get(1));
    }

    static void traverse(int v) {
        moveCount++;
        visited.add(v);

        for (int child : nodes.get(v)) {
            if (child != -1) {
                traverse(child);
                moveCount++;
            }
            if (visited.size() == N && v == lastNode) {
                System.out.println(moveCount);
                System.exit(0);
            }
        }
    }

}