[백준] 17472번 - 다리 만들기2 (Java)
⬛ 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net ⬛ 풀이 최소신장트리(MST) 문제이다. 프로그램 전체 로직은 다음과 같다. 1. bfs를 사용해 섬 별로 번호를 붙여 country[][]를 생성한다. 2. country[][]를 탐색하여 0이 아닐 시(섬이면) 4방을 탐색하고 만약 0이라면 해당 섬의 가장자리라는 뜻이다. 3. 해당방향으로 다리 생성을 시도하고 성공한다면 Bridge를 생성하여 pq에 삽입한다. ..
Algorithm/백준
2021. 9. 15.
