다리만들기
-
[Java] 백준 2146 다리만들기Programming/Algorithm 2021. 2. 25. 20:08
문제 설명 섬과 바다가 있는 지도가 주어진다. 섬과 또 다른 섬을 잇는 다리를 만든다고 할 때, 가장 짧은 다리의 길이를 출력하라. 풀이 각 섬을 그룹화하여 번호를 붙이는 것은 어렵지 않았지만, 최단경로를 구하는 부분에서 어려움이 있었다. 최단경로를 구하는 메서드의 로직을 처음 푼 방식과 추후 수정한 방식 2가지로 정리해보았다. 1. (처음 푼 방식) 섬 1개를 기준으로 탐색하여 다른 섬을 발견하면 탐색을 멈추는 방식 - 최단경로를 구하기 위해서 이동거리를 담을 배열 visited를 Integer.MAX_VALUE로 초기화한다. int[][] visited = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { visite..