코딩성장스토리

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름은 가중치가 들어간 그래프(트리)를 탐색해서 가장 큰 값을 구하는 거다. 그러기 위해선 가장 위에 있는 루트 값을 알아내야 한다. 그리고 그 루트에서 가장 큰 값을 구하면 그게 가장 큰 값이 된다. 즉 루트를 알아내기위한 탐색 1번과 루트를 기준으로 가장 큰 값을 구하는 탐색 2번이면 구해진다. #include #include #include #include #inclu..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 이번에는 노드의 부모노드 번호를 구하는 문제이다. 나는 이 문제를 DFS로 풀었고 탐색을 진행하면서 각 노드에 해당하는 부모를 부모노드 배열에 넣었다. 그래서 한번의 탐색으로 각 노드의 부모를 저장한 배열을 구할 수 있다. #include #include #include #include using namespace std; #pragma warning(disable : 4996) vector d[100020]; //각 인덱스 별로 연결된 노드 배열 bool c..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제는 각 섬마다 그룹화가 필요하다. 그 이유는 최단 거리를 구하기 위해서 DFS를 이용해야 하는데 그냥 돌려버리면 최단거리가 아닌 각 섬에서 출발하여 중간에서 만나는 거리가 구해지기 때문이다. 즉 섬마다 그룹을 나눈다음에 각 섬끼리의 최단거리를 각각 구해야한다. 즉 이 문제는 DFS를 각 섬의 개수만큼 돌려서 최단거리를 구하면 된다. #include #include #include using na..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이 문제는 DFS와 BFS의 개념을 이용하고 푸는 문제이다. 이에 대한 개념은 자료구조의 그래프 부문에 설명되어 있다. #include #include #include #include #include #define PI 3.1415926535 using namespace std; bool check1[1001] = { 0 }; bool check2[1001] ..