코딩 일지

깊이 우선 탐색깊이 우선 탐색(DFS, Depth - First - Search)란, 한 분기를 모두 탐색하고 다음 분기를 탐색하는 방법이다.브루트포스백트래킹주로 이 두 문제를 풀 때 사용한다.재귀함수와 비슷하다.단순 속도로 따지면 BFS보다 느리다.dfs로 탐색하면13 -> 6 -> 11 -> 17 -> 31 -> 7 -> 8 -> 21 -> 19순으로 탐색한다.#include#includeusing namespace std;vector tree[100]; // 각 노드의 인접 리스트를 저장할 벡터 배열int visit[100]={0,}; // 노드 방문 여부를 체크할 배열, 초기값은 0(방문하지 않음)// 깊이 우선 탐색(DFS)을 수행하는 함수void dfs(int n){ if(visit[n..

문제 출처https://www.acmicpc.net/problem/2606실버3 유니온 파인드 또는 dfs 문제이다. dfs로 푸는 풀이는 경우가 많지만,이 문제와 같은 경우는 1번 컴퓨터와 연결되어있는지 안되어있는지만 확인하면 되는 문제이므로유니온 파인드를 이용한 풀이도 가능하다.유니온 파인드에 관한 해설은 아래 링크를 참고하면 된다.https://codingul1234.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find [알고리즘] 유니온 파인드 (Union-Find)유니온 파인드유니온 파인드 (Union-Find)란, 합 집합을 만드는..

문제 출처https://www.acmicpc.net/problem/1167 1167번: 트리의 지름트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지www.acmicpc.net골드 2 트리 문제이다. 임의의 두 점 사이의 거리 중 가장 긴 것을 찾으면 되기에 dfs를 사용했다. 정점 1에서 탐색을 했을 때 가장 길이가 긴 정점은 11을 갖는 5이다.정점 2에서 탐색을 했을 때 가장 길이가 긴 정점은 10을 갖는 5이다. 내가 정점 1을 기준으로 가장 긴 길이를 찾아내도록 풀었다면 위 예제는 문제없이 11이라는 답이 제대로 나오지만정점 2를 기준으로 ..