문제 문제 바로가기> BOJ 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 1. 섬 (2 ≤ 섬의 개수 ≤ 6) 에 대표 번호? 를 매겨주었다. 어떤 섬에서 어떤 섬으로 이어지는 다리인지 알기 위해서! 2. 문제에서 준 조건인, ▷ 다리의 길이 > 2 ▷ 중간에 방향 변화 불가 를 만족 시키는 다리(edge)가 이어주는 섬 두개 (from, to), 다리 길이(len)를 pq에 넣어준다! 이 때, 상 하 좌 우 탐색을 모두 진행하면, 중복되는 edge들..

Union-Find Disjoint set (서로 중복되지 않는 부분 집합들로 나눠진 원소 정보를 저장/조작하는 자료구조)을 표현할 때 사용하는 알고리즘으로, 두 node가 같은 집합에 속하는지 판별할 때 유용하게 사용할 수 있다! 구현 1. 초기화 다음과 같이 모든 값이 자기 자신을 가리키도록 초기화해준다! 모든 값이 자기 집합의 대표값?이 되는 것이다. 처음에는 각 집합의 원소가 하나니까 어찌보면 당연한 일이다. int root[1000001]; for(int i=1; i>n>>m; for(int i=0; ioper>>a>>b; if(oper == 0) union_(a, b); else if(find_(a)==find_(b)) cout

문제 문제 바로가기 > BOJ 10021번: Watering the Fields 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 풀이 모든 필드를 최소 비용으로 연결하기 위하여 MST(최소 신장 트리)를 만들어서 문제를 풀..