트리

문제 링크 : https://www.acmicpc.net/problem/1991 이 문제는 이진트리를 활용해서 푸는 문제이다.문제에 들어가기 전 이진 트리에 대해 알아보자 이진 트리에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있다.편향 이진 트리는 노드들이 한쪽으로 편향돼 생성된 이진 트리이고,포화 이진 트리는 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리,완전 이진 트리는 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은왼쪽부터 채워진 트리이다. 보통 이렇게 트리를 배열로 표현하는 것이 일반적인데 이렇게 했을 때편리한 점은 아래 정리한 표와 같이 부모 노드, 자식 노드들의 인덱스값을 편하게 계산할 수 있다.이동 목표 노드인덱스 연산제약 조건(N = 노드 개..

문제 링크 : https://www.acmicpc.net/problem/1068 문제 자체는 리프노드의 개수를 세는 문제로 단순하다.하지만 단순 리프노드를 세는 게 아닌 중간에 노드를 삭제했을 때 리프노드의 개수를 구해야 한다. 문제를 2가지 방법을 해결해봤다.첫 번째 방법첫 번째는 자식노드의 개수를 직접 카운팅 하여 자식노드가 없는 노드의 개수를 세는 방식이다.먼저 노드를 삭제하기 이전의 자식노드 개수로 counts배열을 초기화한다.이후 만약 2번 노드를 삭제한다면 2번 노드의 부모노드인 0번 노드의 자식개수를 1개 빼준다.그다음 2번 노드와 2번 노드의 자식들은 자식노드의 개수를 -1로 바꿔준다. package boj;import java.util.*;import java.io.*;public cla..

문제 링크 : https://www.acmicpc.net/problem/11725 이 문제는 트리를 구현하는 기본적인 문제이다.루트노드가 1번으로 고정되어 있기 때문에 그저 양방향 인접 리스트로 그래프를 표현하고1번 노드부터 탐색하며 부모노드를 찾아주면 된다. 예제 입력 1번을 그래프로 표현하면 위와 같다.여기서 루트노드가 1번이기 때문에 루트노드부터 시작해서4번 노드의 부모는 1번, 6번 노드의 부모는 1번2번 노드의 부모는 4번, 7번 노드의 부모는 4번이런 식으로 순차적으로 부모를 찾아주면 된다.이 과정에서는 DFS나 BFS를 사용하면 된다. 그래프를 리스트로 표현할 때는 방향이 없는 간선이므로 이와 같이 인접리스트로 표현해주면 된다. package boj;import java.util.*;impo..