투투

문제 어떤 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져있다. 각 길은 유지비가 들고있으며 마을을 두 개의 마을로 분할할 계획을 갖고있다. 마을에는 집이 하나 이상 있어야하고 분리된 두 마을 사이에 있는 길들도 필요없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있을 때 나머지 길 유지비의 합을 최소로 되도록 하라. 입력 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는..

문제 무방향 그래프가 존재할 때 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 이때 반드시 두 개의 정점을 통과하여 N까지 이동하는 최소 경로를 구하라. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 출력 첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다..

문제 모든 길에 가로등이 켜져있는데 어떠한 가로등을 소등하면 하루에 길의 미터 수만큼 절약할 수 있다. 하지만 어떤 두 집을 왕래할 때 불이 켜져있지 않다면 위험하다. 따라서 도시에 있는 모든 두 집 쌍에 대해 불이 켜진 길만으로 서로를 왕래할 수 있어야한다. 이 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오. 입력 여러 개의 테스트 케이스가 주어진다. 첫째 줄에는 집의 개수 M과 길의 수 N이 주어진다. 만약 M과 N이 0이라면 더 이상의 테스트 케이스는 없다. 이어서 N개의 줄에 길에 대한 정보가 입력되고 x, y, z로 이루어진다. x번과 y번 집 사이에 양방향 도로가 있으며 z미터라는 의미이다. 출력 각 테스트 케이스마다 절약할 수 있는 최대 비용을 출력한다. 접근 모든 두 집 쌍에 대해 ..

문제 N개의 도시가 있다. 특정 두 도시사이에는 길이 있을 수도, 없을 수도 있다. 이때 여행하려고하는 도시의 경로가 주어졌을 때 해당 경로가 가능한지 알아보자. 같은 도시를 두 번 이상 방문하는 것도 가능하다. 입력 첫째 줄에 도시의 수 N을 입력하고, 이어서 여행 계획에 속한 도시의 수 M을 입력한다. 그 다음 줄부터 N개의 줄에 도시의 연결정보를 2차원 리스트로 표시하고 연결이 안된 것은 0, 된 것은 1로 표시한다. 가장 마지막 줄에는 여행 경로를 나타내는 도시 M개를 입력한다. 출력 입력된 여행 경로가 가능하면 YES, 불가능하면 NO를 출력한다. 접근 만약 A->B->C의 여행경로가 있다고 했을 때 B와 C가 A에 속해져있으면 이 여행경로로 가능하고, 다른 그룹에 속해있다면 불가능한 것이다. ..

문제 N대의 컴퓨터를 모두 연결하는 네트워크를 구축하려고 한다. 이때 각각의 컴퓨터를 연결하는데 비용이 들기 때문에 N대의 컴퓨터를 연결하는데 드는 최소 비용을 구하라. A->B이고 B->C이면 A->C가 된다고 한다. 입력 첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다. 둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다. 셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다. 출력 모든 컴퓨터를 연결..

문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와..

문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 출력 첫째 줄부터 V개의 줄..

문제 그래프가 주어졌을 때 그 그래프의 최소 스패팅 트리를 구하라. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다. 출력 첫째 줄에 최소 스패닝 트리의 가중치를 출력한..

www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 접근 사각형을 제외한 부분의 개수와 그 영역의 칸 수를 구해야한다. 먼저 이차원 리스트에 직사각형 부분의 좌표에 0이 아닌 수로 표시를 한다. 이렇게되면 0인 부분이 구해야하는 영역이된다. 이후 2차원 리스트를 탐색하여 0을 만날 때마다 BFS 또는 DFS로 탐색을 하고 각 칸의 수를 기록한다. 구현 graph라는 2차원 리스트에 직사각형을 표시한다. 문제에서 주어지는 예시그림에서 상하반전된..

문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다. 출력..