개발하는 고라니

14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net [최소 스패닝 트리(Minimum Spanning Tree, MST), 크루스칼] 남초와 여초만을 이어주는 경로만 존재한다고 생각하면 쉽다. 문제에서 2번째 줄에 M W W W M 이런 식으로 주어지는데, 이를 boolean[ ]에 저장을 한다. 예를 들어 1번 째 학교가 M(남초) 이면 true, 2번 째 학교가 W(여초)이면 false 이런 식으로. 그럼 간선 정보가 주어질 때 선별적으로 간선을 저장할 수 있다. for..

코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr [Minimum Spanning Tree(MST), Kruskal 사용] 시작 정점, 도착 정점, 가중치 이렇게 3개의 멤버변수를 갖는 클래스 Edge를 선언하고 sort()를 이용하기 위해 Comparable 인터페이스를 구현한다. static class Edge implements Comparable{ int h, tg, d; public Edge(int home, int target, int dist){ h=home; tg=target; d=dist; } @Override public int compareTo(Edge o) { return d-o.d; }..

1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net [Kruskal Algorithm] n개의 우주신과 황선자씨의 좌표를 받고, 각 n개의 정점에 대해 이중루프를 돌며 간선을 만들어준다. 이 때 하나의 정점 v는 n-1개의 간선을 갖는다. 만들어진 모든 간선 정보를 List에 담는다. m개의 정점간 연결 정보를 받으며 주어진 정점들은 연결되었다고 parent 배열에 표기한다. List를 정렬하고, 크루스칼 알고리즘을 통해 모든 정점을 연결한다. # Code public class Mai..

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net * 문제 부분이 너무 길어 생략 # 예제 입력 7 8 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 # 예제 출력 9 [Labeling + BFS + Kruskal (+ Union-Find)] 이전에 각 원소가 0과 1 중 한 값을 갖는 N x M 행렬이 주어지는 BFS/DFS 문제에서 자주..