[백준]알고리즘_이진트리(+백준 11725번)
이진트리: 각 노드가 왼쪽 자식과 오른쪽 자식 둘다 갖는 트리!
이때 두 자식 가운데 한쪽이 없거나 둘다 없는 노드가 포함되도 가능(2개이하면 다 된다는 말)
완전이진트리는 루트에서 아래쪽으로 내려가는 노드가 빠짐없이 채워져있고, 왼쪽에서 오른쪽으로 가는 노드도 빠집없이 채워져 있는 이진트리(마지막 제외)라고 할 수 있음!!!
트리/그래프는 비선형알고리즘으로 스택/큐와 달리 1:m 관계가 가능하다. 노드와 간선으로 이루어져 있으며, 루트 노드가 존재하여 방향성이 존재함. (스택, 큐도 시간나면 다시 정리해봐야디,,,, )
+ 간단한 용어정리
루트 노드(가장 윗부분) / 리프 노드(가장 아랫부분.자식x) /
자식 노드(어떤 노드에서 연결된 아래쪽 노드)-부모 노드(어떤 노드에서 연결된 위쪽 노드)-형제 노드(부모==) /
레벨(루트에서 떨어져있는 값: 레벨0/레벨1/… 줄로 보면됨) / 깊이(루트에서 가장 멀리 떨어진 리프까지의 거리) / 차수(노드가 갖는 자식의 수)
자바에서 트리를 구현하기 위해서 배열/리스트/클래스 등을 사용한다. (클래스는 생략)
1) 배열
왼쪽 트리는 배열로 구현을 하면 다음과 같고 b트리를 기준으로 부모/왼쪽자식/오른쪽자식을 구현하는 방법을 설명하였다!
2차원 배열은 다음과 같이 2가지 방식으로 표현이 가능하다.
왼쪽 방식은 하나의 노드를 기준으로 자식 왼쪽/오른쪽에 있는 각각의 노드 번호를 left/right 에 배열함. 자식노드가 없는 경우는 -1로 표시함 / 오른쪽 노드는 n*n형태로 배열을 만든후에 노드가 연결된 곳에 1표시함
2)리스트로 구현: 대부분 리스트로 구현을 한다
위의 동일한 트리를 리스트로 구현하면 다음과 같다. 이 역시 자식노드를 리스트 안에 넣어두고 없으면 빈칸!
백준 11725번
문제: 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오
입력: 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
해결방법
대부분 자바에서 트리는 리스트로 구현하므로 리스트로 구현을 함.
(Main 전까지)
ArrayList<Integer> tree [] >> 리스트로 구현한 트리
int N : ArrayList의 개수를 ㅂ다는 정수 필요함
isvisited : 노드를 방문했는지 확인하는 것
int parent: 부모 노드 리스트 생성
Search 클래스 >> 노드 처음부터 tree에 노드끝까지 방문. 방문 안했을 경우 continue(계속 방문)
parent 리스트에 각 노드 인덱스 저장해줌( + node는 부모노드 >> nextnode(자식노드))
Main부분
main부분은 다음과 같다!
위에서 지정한 변수를 main부분에서 다시 쓰기 > 반복문 돌려서 리스트에 넣고 > u.v로 받아서 리스트 연결 > 잘 받았는지 리스트 한번 넣어보기 > 부모노드 출력하기
마지막에 부모 노드 출력시 i=2 부터 시작하는 이유는 첫번째 노드(루트 노드)는 부모 노드가 없기 때문에 i=2부터 시작하여 반복문을 돌려준다.