알고리즘/백준
[BFS/DFS/MST] 백준 17472번 다리 만들기2 - JAVA
제목부터 무시무시한 문제이다. 무려 BFS / DFS / MST가 모두 쓰이는 문제! 1. 출처 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 드디어 맞췄다!!! 흑흑 오랜만에 알고리즘을 다시 접하니 까먹은 것도 있어서 다시 공부하고... 다시 풀어보았다. 2. 설계 이 문제는 많은 분들이 3step으로 푸는 문제이다. step 1. 섬을 구분한다 -> BFS step 2. 다리를 만들 수 있는 모든 가짓수를 구한다 -> DFS step 3. 모든 섬을 연결할 수 있는 최소 길이의 다리 ..
