BEAKJOON / 백준 - JAVA 1991번 트리 순회

2024.07.16기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 입력된 노드의 관계를 이용해 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제입니다.

 

문제의 예제를 통해 설명을 들어가도록 하겠습니다.

// 예제
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

 

1. 우선 입력 받은 노드들을 숫자로 변환해 2차원 배열에 저장을 해주었습니다.

// 노드를 저장할 배열
node = new int[27][2];

int n, l, r;
StringTokenizer st;
while (t-- > 0) {
    st = new StringTokenizer(br.readLine());

    // 입력 받은 알파벳을 숫자로 변환해 저장
    n = st.nextToken().charAt(0) - 'A' + 1;
    l = st.nextToken().charAt(0) - 'A' + 1;
    r = st.nextToken().charAt(0) - 'A' + 1;

    node[n][0] = l; // 왼쪽
    node[n][1] = r; // 오른쪽
}

 

저장된 노드 배열을 표로 표현한다면 이렇게 생성되게 됩니다.

 

2. 전위 순회를 출력해주는 함수를 호출해줍니다.

// 전위 순회
private static void preorder() {
    Deque<Integer> rq = new LinkedList<>();
    Queue<Integer> lq = new LinkedList<>();
    lq.add(1); // A에서 시작

    int now, l, r;
    while (!rq.isEmpty() || !lq.isEmpty()) {
        // 왼쪽 부터 먼저 확인 후 오른쪽 노드를 확인
        if (!lq.isEmpty()) {
            now = lq.poll();
        } else {
            now = rq.poll();
        }

        // 확인하는 노드부터 출력
        sb.append((char)(now + 'A' - 1));

        l = node[now][0];
        r = node[now][1];

        if (l > 0) { // 왼쪽에 있으면
            lq.add(l);
        }

        if (r > 0) { // 오른쪽에 있으면
            rq.addFirst(r);
        }
    }
}

 

 A가 나오면서 B, C가 추가됩니다.

(현재 문자열 : A)

왼쪽 노드 부터 먼저 탐색하기 때문에 다음은 B가  나오면서 왼쪽 노드에 D가 들어가게 됩니다.

(현재 문자열 : AB)

 

D가 나오면서 왼쪽 노드에 큐가 비어지게 됩니다.

(현재 문자열 : ABD)

왼쪽 노드가 비어 있기 때문에 C가 나오게 되면서 왼쪽 노드에 E를 오른쪽 노드에 F를 추가합니다.

(현재 문자열 : ABDC)

왼쪽 노드에 E가 있기 때문에 다시 왼쪽 노드에서 E가 빠지고 연결된 노드가 없기 때문에 추가가 되지 않습니다.

(현재 문자열 : ABDCE)

왼쪽 노드가 비어있기 때문에 오른쪽 노드에서 F가 나오면서 오른쪽 노드에 G가 추가 됩니다.

(현재 문자열 : ABDCEF)

마지막으로 G가 오른쪽 노드에 나오면서 왼쪽 노드, 오른쪽 노드 둘 다 비어있게 되며 함수가 종료됩니다.

(현재 문자열 : ABDCEFG)

 

3. 중위 순회를 출력해주는 함수를 호출해줍니다.

// 중위 순회
private static void inorder() {
    String result = null; // replaceAll을 위해 String으로 선언
    StringBuilder s;
    Queue<Integer> lq = new LinkedList<>();
    Deque<Integer> rq = new LinkedList<>();
    lq.add(1); // A에서 시작

    int now, l, r;
    while (!lq.isEmpty() || !rq.isEmpty()) {
        // 왼쪽 노드 부터 확인 후 오른쪽 노드 확인
        if (!lq.isEmpty()) {
            now = lq.poll();
        } else {
            now = rq.poll();
        }

        l = node[now][0];
        r = node[now][1];

        s = new StringBuilder();
        if (l > 0) { // 왼쪽 노드가 있다면 순서대로 입력
            lq.add(l);
            s.append((char)(l + 'A' - 1)).append((char)(now + 'A' - 1));
        } else { // 없다면 루트만 입력
            s.append((char)(now + 'A' - 1));
        }

        if (r > 0) { // 오른쪽 노드가 있다면 그 다음에 추가
            rq.addFirst(r);
            s.append((char)(r + 'A' - 1));
        }

        if (result == null) { // 문자열이 없다면 그대로 적용
            result = s.toString();
        } else { // 있다면 해당하는 노드를 (왼쪽)(루트)(오른쪽)으로 변환
            result = result.replaceAll(String.valueOf((char)(now + 'A' - 1)), s.toString());
        }
    }

    // 변환이 끝난 문자열을 출력
    sb.append(result);
}

 

처음 A가 나오면서 왼쪽 노드에는 B, 오른쪽 노드에는 C를 추가 후 문자열을 만들어 줍니다.

 

B가 나오면서 오른쪽 노드에 D를 추가하면서 B가 문자열 DB로 변환됩니다.

그 다음 추가된 D가 나오면서 추가로 추가된 노드는 없이 진행됩니다.

(D는 D로 바꿔도 똑같기 때문에 넘어가도록 하겠습니다.)

 

왼쪽 노드가 비어 있기 때문에 그 다음 오른쪽 노드에서 C가 나오면서 왼쪽에는 E, 오른쪽에는 F가 들어가게 됩니다.

왼쪽에 E가 있기 때문에 E가 나오면서 연결된 노드가 없어 그대로 출력하게 됩니다.

마지막 F가 나오면서 오른쪽 노드에 G를 추가하면서 F가 FG로 변하게됩니다.

4. 후위 순회를 출력해주는 함수를 호출해줍니다.

// 후위 순회
private static void postorder() {
    StringBuilder post = new StringBuilder(); // reverse를 위해 따로 문자열 생성
    Queue<Integer> rq = new LinkedList<>();
    Deque<Integer> lq = new LinkedList<>();
    rq.add(1); // A에서 시작

    int now, l, r;
    while (!rq.isEmpty() || !lq.isEmpty()) {
        // reverse를 하기 때문에 오른쪽 노드 확인 후 왼쪽 노드 확인
        if (!rq.isEmpty()) {
            now = rq.poll();
        } else {
            now = lq.poll();
        }

        // 확인한 문자열 순서대로 저장.
        post.append((char)(now + 'A' - 1));

        l = node[now][0];
        r = node[now][1];

        if (l > 0) {
            lq.addFirst(l);
        }

        if (r > 0) {
            rq.add(r);
        }
    }

    // 저장된 문자열을 reverse 후 출력
    sub.append(post.reverse());
}

 

후위 순회를 할 때에는 reverse()를 이용해 출력을 하기 때문에 오른쪽 부터 확인을 해주었습니다.

큐에 들어가 있는 A를 내보내면서 문자열로 저장 후 왼쪽 노드에 B를 오른쪽 노드에 C를 저장해줍니다.

 

이번에는 오른쪽 노드부터 검사를 하기 때문에 오른쪽 노드에 들어가 있는 C를 내보내면서 E, F를 추가해주고 C를 문자열에 저장을 해줍니다.

 

오른쪽 노드에 F가 있기 때문에 F를 내보내면서 오른쪽 노드에 G를 추가 해주고 문자열에 F를 저장합니다.

 

 

오른쪽 노드에 추가된 G가 나오고 연결된 노드가 없기 때문에 문자열에 저장후 넘어가도록 하겠습니다.

오른쪽 노드가 비어있기 때문에 왼쪽 노드에 있는 E를 내보내고 연결된 노드가 없기 때문에 문자열에 저장후 넘어가도록 하겠습니다.

그 다음도 오른쪽 노드가 비어있기 때문에 왼쪽 노드에 있는 B가 나오면서 연결된 마지막 노드 D를 문자열에 저장하게 되고 이 문자열을 reverse()를 통해 바꿔주도록 하겠습니다.

 

5. 이렇게 구해진 전위 순호, 중위 순회, 후위 순회를 출력을 해줍니다.

// 전위 순회 함수 호출
preorder();
sb.append("\n");

// 중의 순회 함수 호출
inorder();
sb.append("\n");

// 후위 순회 함수 호출
postorder();
sb.append(sub.toString());

 

 

 

코드

package Main;

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

public class Main {
	
	static int[][] node;
	static StringBuilder sb = new StringBuilder();
	static StringBuilder sub = new StringBuilder();
	
	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 t = Integer.parseInt(br.readLine());
		
		// 노드를 저장할 배열
		node = new int[27][2];
		
		int n, l, r;
		StringTokenizer st;
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			
			// 입력 받은 알파벳을 숫자로 변환해 저장
			n = st.nextToken().charAt(0) - 'A' + 1;
			l = st.nextToken().charAt(0) - 'A' + 1;
			r = st.nextToken().charAt(0) - 'A' + 1;
			
			node[n][0] = l; // 왼쪽
			node[n][1] = r; // 오른쪽
		}
		
		// 전위 순회 함수 호출
		preorder();
		sb.append("\n");
		
		// 중의 순회 함수 호출
		inorder();
		sb.append("\n");
		
		// 후위 순회 함수 호출
		postorder();
		sb.append(sub.toString());
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 전위 순회
	private static void preorder() {
		Deque<Integer> rq = new LinkedList<>();
		Queue<Integer> lq = new LinkedList<>();
		lq.add(1); // A에서 시작
		
		int now, l, r;
		while (!rq.isEmpty() || !lq.isEmpty()) {
			// 왼쪽 부터 먼저 확인 후 오른쪽 노드를 확인
			if (!lq.isEmpty()) {
				now = lq.poll();
			} else {
				now = rq.poll();
			}
			
			// 확인하는 노드부터 출력
			sb.append((char)(now + 'A' - 1));
			
			l = node[now][0];
			r = node[now][1];
			
			if (l > 0) { // 왼쪽에 있으면
				lq.add(l);
			}
			
			if (r > 0) { // 오른쪽에 있으면
				rq.addFirst(r);
			}
		}
	}
	
	// 중위 순회
	private static void inorder() {
		String result = null; // replaceAll을 위해 String으로 선언
		StringBuilder s;
		Queue<Integer> lq = new LinkedList<>();
		Deque<Integer> rq = new LinkedList<>();
		lq.add(1); // A에서 시작
		
		int now, l, r;
		while (!lq.isEmpty() || !rq.isEmpty()) {
			// 왼쪽 노드 부터 확인 후 오른쪽 노드 확인
			if (!lq.isEmpty()) {
				now = lq.poll();
			} else {
				now = rq.poll();
			}
			
			l = node[now][0];
			r = node[now][1];
			
			s = new StringBuilder();
			if (l > 0) { // 왼쪽 노드가 있다면 순서대로 입력
				lq.add(l);
				s.append((char)(l + 'A' - 1)).append((char)(now + 'A' - 1));
			} else { // 없다면 루트만 입력
				s.append((char)(now + 'A' - 1));
			}
			
			if (r > 0) { // 오른쪽 노드가 있다면 그 다음에 추가
				rq.addFirst(r);
				s.append((char)(r + 'A' - 1));
			}
			
			if (result == null) { // 문자열이 없다면 그대로 적용
				result = s.toString();
			} else { // 있다면 해당하는 노드를 (왼쪽)(루트)(오른쪽)으로 변환
				result = result.replaceAll(String.valueOf((char)(now + 'A' - 1)), s.toString());
			}
		}
		
		// 변환이 끝난 문자열을 출력
		sb.append(result);
	}
	
	// 후위 순회
	private static void postorder() {
		StringBuilder post = new StringBuilder(); // reverse를 위해 따로 문자열 생성
		Queue<Integer> rq = new LinkedList<>();
		Deque<Integer> lq = new LinkedList<>();
		rq.add(1); // A에서 시작
		
		int now, l, r;
		while (!rq.isEmpty() || !lq.isEmpty()) {
			// reverse를 하기 때문에 오른쪽 노드 확인 후 왼쪽 노드 확인
			if (!rq.isEmpty()) {
				now = rq.poll();
			} else {
				now = lq.poll();
			}
			
			// 확인한 문자열 순서대로 저장.
			post.append((char)(now + 'A' - 1));
			
			l = node[now][0];
			r = node[now][1];
			
			if (l > 0) {
				lq.addFirst(l);
			}
			
			if (r > 0) {
				rq.add(r);
			}
		}
		
		// 저장된 문자열을 reverse 후 출력
		sub.append(post.reverse());
	}
}