2146번 다리 만들기(BFS) - ☆

#문제링크 : https://www.acmicpc.net/problem/2146

전략 : 핵심은 1. 섬을 구별하기 위해 번호를 부여해야 한다.     2. 각 섬으로부터 다른 섬까지의 거리를 구한다.

<1st try>

단지번호 부여하기 + 토마토 문제이다. 매우 중요한 문제고 난이도도 상당하다.

먼저 단지번호 부여하기와 같이 각 섬마다 BFS를 실행하여 섬의 번호를 부여한다. map과 check 이외의 추가로

dist라는 하나의 섬으로부터 다른 map영역까지의 거리를 저장하는 배열을 선언한다.

하나의 섬과 나머지 map과의 구분을 위해 선택된 섬의 영역은 0로 하고, dist의 나머지 영역은 -1로 한다.

선택된 섬의 노드를 모두 푸쉬하고, 병렬적으로 BFS탐색을 하여 dist에 섬으로부터의 거리를 작성한다.

거리로 표시된 map의 영역중, map이 1이고(섬이고), check가 다르면(다른 섬이면) ans에 해당 거리를 담는다.

if문으로 그 거리들중 최소값을 ans에 저장한다. 그리고 1을 빼준다. 다른 섬 전까지의 거리가 다리거리이므로

하나를 빼준다.

1. Code

<2nd try>

처음 시도보다 훨씬 빠르게 할 수 있는 방법이 있다. 처음과 같이 우선, 각 섬에 번호를 부여한다. 그리고 각 섬의 영역을 동시에 확장시킨다. 그렇게 영역을 확장시키다 보면 서로 다른 섬끼리 맞닿아 있게 된다. 다리가 놓이는 곳은 바로 이부분이다. 섬의 경계가 지어져 있는 부분에 다리를 놓는 것이다. 그리고 check배열로 각 섬에서부터의 상대적인 거리를 동시에 기록한다. 앞서서 영역을 확장한 것과 같은 원리다. 예를 들어, 1번 섬으로부터 2만큼 떨어져 있고 2번섬으로 부터 2만큼 떨어져 있는 곳이 맞닿아 있다면, 이 경로는 결국 1번섬과 2번섬이 4만큼 떨어져 있다는 소리다. 즉, 다리의 길이가 된다. 결국, 다리의 길이 = A섬으로부터 N만큼 떨어진 부분 + B섬으로부터 M만큼 떨어진 부분 = N + M이 된다. 요점은 "섬의 영역을 섬들이 맞닿을 때까지 확장(병렬) + 각 섬들로부터의 거리 표시(병렬)" 이다. 이렇게 각 배열에 표시가 끝났다면, 섬의 경계인 두 부분에서 같은 행과 열에 위치한 check배열에 들어있는 거리를 둘 다 더해주면 다리의 길이를 구할 수 있고, 이렇게 구한 다리의 길이중에 가장 작은 값이 문제에서 요구하는 답이 된다. 이 방법은 위의 방법보다 빠르다. 왜냐하면 위에선 섬 하나하나를 반복하면서 지도에 해당 섬으로부터 떨어진 거리를 업데이트 하고 또 다시, 맵을 다 훑어보면서 목표한 섬이 출발한 섬과 다르면 거리를 구하고, 또, 그 거리들 중에 제일 작은 값을 답으로 찾는 방식이기에 훨씬 느리다. 반복문이 여러번 호출되기 때문이다.

2. Code