[JAVA] 백준 22856 트리 순회

 

22856번: 트리 순회

 

문제

유사 중위 순회를 하면서 이동한 총 횟수를 출력한다.

풀이

유사 중위 순회를 하면서 이동한 총 횟수를 출력해야 하는데, 여기서 주의할 점은 유사 중위 순회의 종료지점이 일반 중위 순회의 종료 지점일 경우에 종료해야 한다는 점이다.

유사 중위 순회의 종료 지점이 모든 노드를 방문했을 경우로 착각해서 여기서 많이 당황했다.

따라서 문제를 잘 읽어보길 바란다.

📌 값 입력

        StringTokenizer st;
        for(int i=1; i<N; i++){
            st = new StringTokenizer(br.readLine() ," ");
            int now = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[now].add(a == -1 ? 0 : a);
            A[now].add(b == -1 ? 0 : b);
        }

트리의 각 요소들을 단방향 그래프 형태로 구현하였다.

여기서 -1(자식 노드가 없는 경우)일때, 0으로 변경해주었는데 나중에 비교연산을 진행할 때 인덱스 예외를 방지하기 위해서 바꿔주었다.

📌 중위 순회

    static public void inOrder(int now){

        if(A[now].get(0) != 0){
            inOrder(A[now].get(0));
        }
        lastInOrder = now;
        if(A[now].get(1) != 0){
            inOrder(A[now].get(1));
        }
    }

값들을 돌면서 중위 순회를 해주고 중위 순회의 마지막 값만 남겨놓았다.

📌 유사 중위 순회

    static public void similarityInOrder(int now){
        V[now] = true;

        if(A[now].get(0) != 0 && !V[A[now].get(0)]){
            answer++;
            similarityInOrder(A[now].get(0));
        }
        if(A[now].get(1) != 0 && !V[A[now].get(1)]){
            answer++;
            similarityInOrder(A[now].get(1));
        }

        if(lastInOrder == now) flag = true;
        if(flag) return;
        answer++;
    }

유사 중위 순회의 알고리즘은 다음과 같다.

1. 현재 노드의 왼쪽이 존재하고, 방문한 적이 없다면 왼쪽 노드로 이동한다. (answer는 이동 횟수)
2. 현재 노드의 오른쪽이 존재하고, 방문한 적이 없다면 오른쪽 노드로 이동한다.
3. 만약 현재 노드에서 방문할 곳이 남아있지 않고 현재 노드가 일반 중위 순회의 마지막 노드일 경우 flag를 true로 설정하고 종료한다.
4. 만약 현재 노드에서 방문할 곳이 남아있지 않고 flag가 false라면, 부모 노드로 돌아간다. (메서드 종료 + 이동 횟수 추가)
5. 만약 현재 노드에서 방문할 곳이 남아있지 않고 flag가 true라면 이미 종료된 순회기 때문에 이동 횟수를 늘리지 않고 메서드를 종료한다.

📌 전체 코드

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

class Main {
    static ArrayList<Integer>[] A;
    static boolean[] V;
    static int answer = 0;
    static boolean flag = false;
    static int N;
    static int lastInOrder = 1;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine())+1;

        V = new boolean[N];
        A = new ArrayList[N];
        for(int i=1; i<N; i++){
            A[i] = new ArrayList<>();
        }
        V[0] = true;

        StringTokenizer st;
        for(int i=1; i<N; i++){
            st = new StringTokenizer(br.readLine() ," ");
            int now = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[now].add(a == -1 ? 0 : a);
            A[now].add(b == -1 ? 0 : b);
        }

        inOrder(1);
        similarityInOrder(1);
        System.out.println(answer);
    }

    static public void similarityInOrder(int now){
        V[now] = true;

        if(A[now].get(0) != 0 && !V[A[now].get(0)]){
            answer++;
            similarityInOrder(A[now].get(0));
        }
        if(A[now].get(1) != 0 && !V[A[now].get(1)]){
            answer++;
            similarityInOrder(A[now].get(1));
        }

        if(lastInOrder == now) flag = true;
        if(flag) return;
        answer++;
    }
    static public void inOrder(int now){

        if(A[now].get(0) != 0){
            inOrder(A[now].get(0));
        }
        lastInOrder = now;
        if(A[now].get(1) != 0){
            inOrder(A[now].get(1));
        }
    }

}

결과