[Baekjoon]2589.보물섬

2589.보물섬

http://www.acmicpc.net/problem/2589

---

맵이 주어졌을때 두 지점의 최단거리 중 최댓값을 구하는 문제이다. 노드 간 최단 경로를 찾는 문제이므로 bfs를 사용했다.

1. 맵을 순회하며 땅인 지점에서 bfs를 수행.
2. dist배열에 거리 저장.
3. dist배열에서 최댓값을 찾고, 1로 돌아가서 반복.

dist배열은 2차원 배열로 bfs를 시작한 지점으로부터 해당 인덱스까지의 거리를 저장한다. 시작 지점에 따라 최단거리가 다르기 때문에 bfs가 끝나면 초기화해주고 다른 육지 지점으로 가서 다시 bfs를 수행한다.

육지가 위 그림처럼 생겼을때 <그림 a>처럼 1에서 bfs를 수행하면 가장 멀리 떨어진 지점까지 거리는 4이다. 하지만 <그림 b>와 같은 경우가 최댓값을 가진다. 이 점을 잘 생각하여 dist배열 값을 저장하고 bfs가 끝날때마다 최댓값을 갱신시킨다. 

 

<전체코드>