문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 어떻게 풀것인가? 트리 형태를 만든 다음 삭제 노드를 부모 노드와 끊어준다. 노드의 부모는 무조건 1개이기 때문에, 끊어주면 탐색을 할 수 없다. 트리를 DFS 탐색으로 탐색을 진행한다. BFS나 DFS 둘다 되겠지만 구현이 쉬운 BFS를 선택했다. 문제 알고리즘 parent 배열에 각 노드의 parent 값을 저장한다. parent 배열 이용하여 삭제할 노드를 부모 노드에서 제거 한다. BFS 탐색을 진행하면서 leaf 노드를 찾는다. 주의할 점 루..

시도 방법 방법 1 : 위로 올라가면서 비교 (실패) 1. 전위 탐색으로 노드 값이 주어진다 2. 마지막 삽입 노드를 기준으로 추가 해야지 3. 마지막으로 삽입된 노드를 기준으로 점점 올라가면서 비교를 하자 4. "틀렸습니다" 방법 2 : 루트를 기준으로 아래로 내려가면서 적절한 위치에 삽입 (성공) 1. 모든 트리의 왼쪽은 무조건 자기보다 작아야 하고 오른쪽은 무조건 커야하는 규칙이 존재 2. 루트를 기준으로 내려가면서 적절한 위치에 노드를 추가하면 되지 않을까 3. "맞았습니다" 의문점 왜 하나씩 추가해도 문제가 되지 않는지 이해가 안되어서 찾아봄 의문점 1 : 이진 탐색트리는 값에 따라 위치가 무조건 같나? 삽입 순서에 따라 달라지는 건가? 답 : 삽입 순서에 따라 위치는 물론 트리 모양도 달라짐 ..

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 풀이 핵심 1. root 노드를 찾기 2. 가장 가까운 공통 노드 찾기 root 노드 찾기 root 노드를 찾기 위해 입력 자식 노드를 체크 해준다. 그리고 입력이 끝난 후에 체크되지 않은 노드가 root 노드이다. 가장 가까운 노드 찾기 LCA(Lowest Common Ancestor) 알고리즘을 이용한다! LCA 알고리즘의 핵심 순서는 3가지이다. 각 노드의 Depth, Parent 리스트를 구한다. ..

문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 접근 전체 노드를 탐색하면서 어떻게 부모 노드를 저장할 수 있을까! 생각을 해봤을 때 자식 노드를 탐색하기 위해 재귀 함수를 호출할 때 부모의 값을 넘겨주면 될 것이라고 생각했다! 모든 노드를 탐색해야 하기 때문에 DFS와 BFS 중 고민했고 함수를 호출할 때 부모의 값을 넘겨주면 구현하기 쉬울 것이라 생각해서 재귀함수를 쓰는 DFS를 사용했다. void DFS(int child, int p) { visited[child] = true; // 부모 값을 저장 parent.set(child, p); Iterator i..

문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 접근 방법 1번 노드를 시작으로 그래프가 끊길 때까지 전체 탐색을 하면 되는 문제라서 BFS나 DFS 중 아무거나 써도 될 것 같았다. 그래서 잘 안써본 BFS로 구현해봤다! 알게된 점 큐를 구현할 때 LinkedList를 이용해도 된다. add : 맨 뒤에 요소를 삽입한다. poll : 맨 앞(제일 먼저 삽입된 요소) 요소를 제거 후 반환 한다. 코드 import java.awt.*; import java.io.*; import java.util.*; publ..