sncap Style

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄부터 M+1개의 줄에는 A, B(1≤ A,B ≤ N), C 가 주어진다. 이는 A와 B 건물에 연결된 도로가 있다는 뜻이며, C는 0(오르막길) 또는 1(내리막길)의 값을 가진다. 같은 경로 상에 2개 이상의 도로가 주어지는 경우는 없으며, 입 www.acmicpc.net 문제를 이해하는데 한참 걸렸다. 그냥 MST(크루스칼)로 푸는 문제인데.. 단 예외 조건이 있다, 오르막이 0, 내리막이 1로 ..

절단점(cut vertex): 어떤 무향 그래프의 절단점이란 이 점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 2개 이상으로 나뉘어지는 정점을 말한다. 위 그래프에서 1, 3, 5 정점이 각각 절단점이다. 각 지점 별로 탐색하면서, 자식의 depth가 자신의 depth보다 크거나 같다면 단절점이다. root의 경우 child node가 2이상이면 단절점이다. DFS static int dfs(int here, int d, boolean root) { D[here] = d; int ret = D[here]; int child = 0; for (int there: VT[here]) { if(D[there]==0) { child++; int df = dfs(there, d+1, false); if(!r..

https://algospot.com/judge/problem/read/FIRETRUCKS algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 위해 가능한 한 빠르게 소방차를 파견해야 합니다. 서울 시내에는 m개의 소방서가 있습니다. 화재 장소에서 가장 가까운 소방서에서 소방차를 보낸다고 할 때, 각 화재 장소에 소방차가 도달하기까지 걸리는 시간의 합을 계산하는 프로그램을 작성하세요. 각 소방서에는 소방차가 충분 algospot.com 다익스트라의 다른 시각을 볼수 있는 문제로, 기본 사상인 : 한 점에서 시작하여, 여러점의..

https://algospot.com/judge/problem/read/BRAVE algospot.com :: BRAVE 용감한 쿠키군의 폭탄 해체 문제 정보 문제 당신은 용감한 쿠키군을 둘러싼 시한 폭탄을 해체해야 한다. 용감한 쿠키군을 둘러싼 폭탄은 1부터 N까지 번호가 적혀 있는 금속 점을 갖고 있다. 또한, 그 점들 중 일부는 전선들로 이어져 있다. 당신은 주변을 둘러보던 중 테러리스트가 남긴 쪽지를 발견했고, 폭탄의 특징을 알게 되었다. 그 특징들은 다음과 같다. 금속 점 x와 y가 직접 전선으로 연결되어 있으면, x와 y 사이에는 전류가 흐른다. 금속 점 x와 y algospot.com 용감한 쿠키군의 폭탄 해체 생각보다 어렵게 되지는 않았음. Union-find 내에 Union시 Max gr..

https://algospot.com/judge/problem/read/ARCTIC algospot.com :: ARCTIC 남극 기지 문제 정보 문제 남극에는 N 개의 탐사 기지가 있습니다. 남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. 탐사 본부가 다른 모든 기지에 연락을 할 algospot.com N개의 탐사지점중 최소값으로 MST인 지점을 다 찾는지 문제. 이분탐색으로 시도했으나./.. 답이.. P..

https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재한다. 각각 도시는 1번부터 N번까지 번호가 붙여져 있다. 그 중에서 1번 도시의 군주 박건은 모든 도시를 정복하고 싶어한다. 처음 점거하고 있는 도시는 1번 도시 뿐이다. 만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 www.acmicpc.net 단순 MST 인줄 알았는데.. 예외 변수가 하나 있음. 도로 건설시 추가 비용 t가 발생하는데. 조건을 따져 보면. (1~n-1 까지의..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 입력 첫째 줄에 www.acmicpc.net MST를 구하는 문제, 각 별자리 좌표간의 값을 Edge로 넣고 MST를 구하면 됨. n의 개수가 1 ≤ n ≤ 100 인상태라....

https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다. www.acmicpc.net MST로 구하면 될줄 알았는데... 다름 조건 때문에 단순 MST로는 구할수 없다. 최소 개수의 회선만 복구 1번 노드에서 k번 노드의 최단거리가..

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ6497 { static int N, M; static DJS djs; static Edge[] edges; static class Edge implements Comparable{ int s, e, v; Edge(int s, int e, int v) { this.s = s; this.e = e; this.v = v; } @Override public ..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 www.acmicpc.net 최소스패닝트리 구하는 문제로, 모든 간선 추가시, 모든 x,y,z 기준 가중치 정보를 담게되면 O(3 *(N^2))이 되므로 굉장히 큰..