2146번
-
백준 2146번 다리 만들기 :: 마이구미알고리즘 풀이/그래프 2017. 1. 24. 22:52
이번 글은 백준 알고리즘 문제 2146번 "다리 만들기" 를 다뤄본다.이 문제는 BFS DFS 활용 문제이다.하단에 비슷한 문제들이 나열되어 있다.DFS, BFS 관련 글.http://mygumi.tistory.com/102 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나,위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).지도가 주어질 때, 가장 짧은 다리 하..