17472
-
백준 17472번 다리 만들기2PS 2020. 3. 5. 19:51
https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net https://www.acmicpc.net/problem/1260 문제에 대한 감이 아예 안오시면 이 문제를 완전히 이해해야 합니다. 기본적인 그래프 이론 문제입니다. 다리를 연결하는 방법을 전부 고려해야하는 완전 탐색 문제입니다. 우선 n개의 섬을 전부 연결하기 위해서는 최소 n-1개의 다리가 필요합니다. 즉, 다리 n-1개를 선택해야 합니다. 조합으로 선택하면 됩니다. 다..