나만의 작은 도서관

문제 링크https://www.acmicpc.net/problem/1753 난이도 :  골드 4 문제 요약 설명 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선의 개수 E둘째 줄에는 시작 정점의 번호 K셋째 줄부터 E개의 줄: 각 간선을 나타내는 세 개의 정수 (u, v, w)이 주어진다. ( u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻 )입력 제한 정점의 개수 V  (1 ≤ V ≤ 20,000)간선의 개수 E (1 ≤ E ≤ 300,000)시작 정점의 번호 K (1 ≤ K ≤ V)u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사..

문제 링크https://www.acmicpc.net/problem/1197 난이도 : 골드 4 문제 요약 설명그래프가 주어졌을 때, 그래프의 최소 스패닝 트리의 가중치를 구하는 프로그램을 작성하시오.최소 스패닝 트리는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 입력1번째 줄: 정점의 개수 V 간선의 개수 E 다음 E개의 줄: 세 정수 A, B, C ( A번 정점과 B번 정점이 가중치 C인 간선으로 연결) 입력 제한정점의 개수 V(1 ≤ V ≤ 10,000)간선의 개수 E(1 ≤ E ≤ 100,000)0 1,000,000 최소 스패닝 트리의 가중치는 int ..

문제 링크https://www.acmicpc.net/problem/1167 난이도 : 골드 2 문제 요약 설명트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.입력1번째 줄 : 정점의 개수 V이 후 각각의 V개의 줄:정점 번호가 먼저 주어진다.연결된 정점의 번호와 거리가 주어진다.(반복적으로 주어질 수 있다.)마지막에 -1이 입력으로 주어진다.입력 제한정점의 개수 V (2 ≤ V ≤ 100,000)0 입력 예제// input51 3 2 -12 4 4 -13 1 2 4 3 -14 2 4 3 3 5 6 -15 4 6 -1// ans11 풀이 방식1967번 문제와 동일한 문제. 단, 모든 간선은 2번씩 나타난다.(A와 B사이의 간선 1개..

문제 링크https://www.acmicpc.net/problem/1967 난이도 : 골드 4 문제 요약 설명노드 개수가 n개인 트리가 하나 있다. 각 노드는 1부터 n까지 번호가 매겨져 있을 때, 트리의 지름을 구하시오. 지름은 노드 사이의 최대 거리를 의미한다.입력첫 번째 줄: 노드의 개수둘째 줄부터 n-1개의 줄: 부모 노드의 번호, 자식 노드의 번호, 간선의 가중치 입력 제한노드의 개수 n(1 ≤ n ≤ 10,000)0 입력 예제// input121 2 31 3 22 4 53 5 113 6 94 7 14 8 75 9 155 10 46 11 66 12 10// ans45 풀이 방식 임의의 노드를 루트로 하는 트리에서 노드 사이의 최대 거리를 M이라 했을 때, 트리의 지름은 가장 큰 M을 의미한다. ..

문제 링크https://www.acmicpc.net/problem/1916난이도 : Gold 5 문제 요약 설명N개의 정점(도시)과 비용을 가지는 M개의 간선(버스)으로 이루어진 무방향 그래프가 있다. 정점 A에서 정점 B로 가는 최소비용을 구하는 프로그램을 작성해라.입력첫째 줄: 도시의 개수 N둘째 줄: 버스의 개수 M이후 M개의 줄 : 출발 도시 번호, 도착 도시 번호, 버스 비용마지막 줄: 구하고자 하는 출발점의 도시번호, 도착점의 도시번호입력 제한도시의 개수 N(1 ≤ N ≤ 1,000)버스의 개수 M(1 ≤ M ≤ 100,000)0출발점에서 도착점으로 갈 수 있는 경우만 입력으로 주어진다.입력 예제// input581 2 21 3 31 4 11 5 102 4 23 4 13 5 14 5 31 5/..

문제 링크https://www.acmicpc.net/problem/11967 11967번: 불켜기(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으www.acmicpc.net 난이도 :  골드 2 문제 요약 설명N X N개의 방이 있는 정사각형 모양의 헛간이 있다. 헛간에 있는 각 방은 (1, 1)부터 (N, N)까지 번호가 매겨져있다. 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 ..