📙[Algo] 24.04.09 알고리즘

알고리즘 문제) BOJ 2250. 트리의 높이와 너비

• 링크 : https://www.acmicpc.net/problem/2250

문제 요약

• 이진트리를 격자에 다음과 같은 규칙에 따라 그림
  • 같은 레벨에 있으면 같은 행
  • 한 열에는 오직 한 노드만 존재
  • 임의 노드의 왼쪽 서브트리 노드들은 해당 노드보다 왼쪽 열, 오른쪽 서브트리 노드들은 오른쪽 열에 위치
  • 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이에 비어있는 열은 없다.
• 임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성
  • 너비 : 각 레벨의 노드들 중 가장 오른쪽 노드 x좌표 값 - 가장 왼쪽 노드 x좌표값 + 1
  • 여러개가 있다면 레벨이 작은 걸로 출력

시간 제한

• 1초

입력

• 노드 개수 나타내는 정수 N
  • 1≤N≤1만
• N개의 줄에 노드 번호와 해당 노드 왼쪽 자식 노드, 오른쪽 자식 노드 번호 주어짐
  • 노드 번호는 1부터 N까지
  • 자식이 없으면 자식 노드 번호에 -1

출력

• 첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력
  • 두 개 이상 있을 때에는 번호가 작은 레벨을 출력

접근법

• 각 노드의 x좌표를 구해야할까?
• 같은 레벨에 위치한 노드들의 부모 노드끼리도 서로 같은 레벨…
• 일단 dfs로 parent배열에 각 노드별 부모 노드를 기록한다.
  • 이때 원소가 0인 애가 최상위 루트 노드가 된다.
• 그리고 3번 조건에 의하면 루트 노드 기준 가장 중위 순회 진행 했을 때 가장 왼쪽 끝에 도착하는 자식의 x좌표 위치가 1이 된다.
  • 그래서 해당 노드를 기준으로 중위 순회 진행하면서 x좌표를 하나씩 늘려가며 기록한다.
    • 주의할점은 뿌리노드를 발견하면 해당 노드 기준 오른쪽 서브트리의 가장 왼쪽 자식 노드가 그 다음 x좌표 값을 갖게 된다
• 중위순회 메소드를 구현한다 ⇒ 해당 노드 기준 Left Node 부터 방문(-1이 나올 때까지) ⇒ 가장 왼쪽 노드에 도달했다면 가장 가까운 부모 노드(뿌리) 방문 ⇒ 부모 노드 기준 Right Node 방문

코드

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

public class Main {
    static int N;
    static ArrayList<Integer>[] list;
    static int[] parent;
    static int root;
    static ArrayList<Integer>[] posY;
    static int[] posX;
    static int x = 1;

    static void inorder(int cur, int y) {
        int leftNode = list[cur].get(0);
        int rightNode = list[cur].get(1);

        // 행 위치 기록
        posY[y].add(cur);

        if (leftNode != -1) inorder(leftNode, y + 1);
        // 열 위치 기록
        posX[cur] = x++;
        if (rightNode != -1) inorder(rightNode, y + 1);
    }

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

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

        list = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        int ro, le, ri;
        parent = new int[N + 1];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            ro = Integer.parseInt(st.nextToken());
            le = Integer.parseInt(st.nextToken());
            ri = Integer.parseInt(st.nextToken());

            list[ro].add(le);
            list[ro].add(ri);

            // 부모 노드 기록하기 -> 여기서 주의(처음에 dfs로 찾는 것보다 그냥 입력받을 때 기록)
            if (le != -1) parent[le] = ro;
            if (ri != -1) parent[ri] = ro;
        }

        // 최상위 뿌리 노드 찾기
        for (int i = 1; i <= N; i++) {
            if (parent[i] == 0) {
                root = i;
                break;
            }
        }

        // x,y좌표 기록하기
        posY = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            posY[i] = new ArrayList<>();
        }
        posX = new int[N + 1];
        inorder(root, 1);

        int max = 0, level = 0, lidx, ridx, dist;
        for (int i = 1; i < N + 1; i++) {
            if (posY[i].isEmpty()) break;

            lidx = posY[i].get(0);
            ridx = posY[i].get(posY[i].size() - 1);

            dist = posX[ridx] - posX[lidx] + 1;

            if (max < dist) {
                max = dist;
                level = i;
            }
        }

        bw.write(level + " " + max);
        bw.flush();
        bw.close();
        br.close();
    }
}