Coding_Test_C++
BaekJoon 1167번: 트리의 지름
트리의 지름을 구하는 알고리즘이다. BFS를 써서 문제를 해결하고자 했으나 마땅한 방법이 생각나지 않아 다른 블로그의 힘을 빌렸다. blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를 blog.myungwoo.kr 풀이법 1) 아무 노드 a (이 코드의 경우 1)를 이용해서 a에서 가장 먼 점인 x를 구한다. 2) x에서 가장 먼 노드인 y를 구하고 x-y 간의 거리를 구한다. (지름 구하기) 3) BFS를 이용하여 vistied 배열과 dist 배열을 사용하여 문제를 해결한다. 이 때 초기화를 잊지 말자..
BaekJoon 11725번: 트리의 부모 찾기
DFS를 이용해서 풀 수 있는 알고리즘이다. DFS를 구현할 시 중요한 것은 1) 방문한 정점을 알아야 한다. 2) 더 이상 방문할 정점이 없으면 이전 정점으로 돌아간다. 3) 그래프가 분리되어 있을 수 있으므로 이를 꼭 확인해야 한다. DFS의 장점은 1) 현재 경로 상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다. 2) 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있다. 3) BFS보다 구현이 간단하다. DFS의 단점은 1) 단순 검색 속도는 BFS보다 느리다. 2) 해가 업는 경우 빠질 가능성이 있다. (임의의 깊이를 지정한 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로를 탐색한다) 3) 깊이 우선 탐색은 해를 구하면 종료된다. 고로 구한 해가 최단 경로가 된다..