tose33

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 기본적인 크루스칼 알고리즘 문제.

https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net 백트래킹 문제. 모든 칸에 대하여 모든 방향을 시도해 보면서 방문한 칸의 갯수가 빈 칸의 갯수와 같아질때가 모든 칸을 방문한 시점이므로, 최소 이동 횟수를 갱신해 주면 된다. 특별히 조심할 점은 없는 구현 문제였다.

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 모든 리프 노드들에 대하여 깊이 우선 탐색으로 다른 노드들까지의 거리를 구하면 된다. 구한 거리중 가장 큰 값이 답이다. 풀고난후 다른 분들의 코드를 살펴봤는데 트리의 지름을 구하는 방법이 있었다. 1) 임의의 노드 a에서 가장 먼 노드b를 찾는다. 위 그림에서 임의의 노드를 5로 정하면 가장 먼 노드는 거리 11+9+10=30인 노드 12이다. 2) 찾은 노드 b에서 가장 먼..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 가로와 세로의 최대 크기가 50이기 때문에 모든 땅에 대해서 bfs로 다른 땅과의 최단 거리를 구하면서 가장 거리가 먼 땅들을 계속해서 갱신해 주면 된다.