[java]트리의 높이와 너비 - 백준2250

문제

• 트리의 높이와 너비(백준2250)

풀이

문제 해석을 하자면,

• 트리는 이진트리이며, 제일 큰 너비를 구하는 문제이다.

풀이

• 구글링의 힘을 조금 빌린 문제 ㅜㅜ
• 전위, 중위, 후위순회 중에서 중위순회가 트리를 보면 왼쪽에서 -> 오른쪽으로 점점 나아가는 형태임을 알 수 있다.
• 이러한 특징 덕분에 중위순회를 통해서 첫시작과 끝을 비교해서 구할 수 있다.
• 본인은 중위순회하면서 따로 level 배열에 시작점 길이와 끝점 길이를 기록해둘 생각이다.
  => level 배열의 index는 실제 트리의 각 정점 높이를 의미
• 마지막에는 비교를 통해서 너비가 제일 큰 값을 출력한다.
• 참고 : 루트가 1이 고정인줄 알았다가 아니였단걸 알게 되었다… 루트는 1개니까 노드개수로 구하자..!

코드

/*
아래 테스트케이스처럼 루트가 1이 무조건 고정이 아님..!
5
2 1 3
1 4 -1
4 -1 -1
3 5 -1
5 -1 -1
극단적인 케이스도 확인
1
1 -1 -1
 */
static List<Node>[] inArr = new ArrayList[10005];
static int[][] level = new int[5010][2];
static int width = 1;
static int[] findRoot = new int[10005]; // root 노드 찾기용

public static void inOrder(int root, int height) {
    if(root == -1) return;
    Node node = inArr[root].get(0);
    inOrder(node.left, height+1);
    if(level[height][0]==0) { // 시작점은 처음에만
        level[height][0] = width;
        level[height][1] = width; // 끝점도 미리 init (나중에 너비계산에 오류없기 위함)
        width++;
    }
    else {
        level[height][1] = width; // 끝점은 계속 갱신(제일 마지막이 젤 큰값
        width++;
    }
    inOrder(node.right, height+1);
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    int N = Integer.parseInt(br.readLine());
    for(int i = 0 ; i<=N; i++) inArr[i] = new ArrayList<>(); // init
    for(int i = 0 ; i<N;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());
        inArr[a].add(new Node(b, c));
        findRoot[a]++;
        if(b!=-1) findRoot[b]++;
        if(c!=-1) findRoot[c]++;
    }
    // run => 참고로 이진트리
    int root = -1;
    for(int i = 1 ; i<=N; i++) {
        if(findRoot[i]==1) {
            root = i;
            break;
        }
    }
    inOrder(root, 1);

    // output
    int height = 1;
    int resultLevel = 0;
    int resultWidth = 0;
    int prev = 0;
    while(true) {
        if(level[height][0] == 0) break;
        prev = resultWidth;
        resultWidth = Math.max(resultWidth, level[height][1]-level[height][0]+1);
        if(prev != resultWidth) resultLevel=height;
        height++;
    }
    System.out.print(resultLevel);
    System.out.print(' ');
    System.out.println(resultWidth);
}
static class Node {
    int left, right;
    public Node(int left, int right) {
        this.left = left; this.right = right;
    }
}

느낀점

다시 풀어보자.