Baekjoon 2589 보물섬 JAVA

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

2589번: 보물섬

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202589

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 map가 주어졌을 때 육지에서 갈 수 있는 최단거리 중 가장 먼 두지점에 보물이 묻혀있다고 할 때

가장 먼 두지점의 거리를 구하는 문제다.

 

처음 문제를 보고 육지를 방문하면 bfs 한번 돌려서 가장 먼 지점에서 다시 bfs를 돌려서 길이를 갱신하면 되겠다고

생각하고 문제를 보다가 범위가 별로 안 커서 그냥 각 칸마다 bfs를 돌려서 최대 거리를 갱신하는 방식으로

문제를 해결했다.

 

먼저 입력 처리를 해준 뒤, 육지인 칸에 대해서 bfs를 모두 돌려준다.

각 육지마다 방문 배열을 초기화해줘야 하기 때문에 bfs안에 선언해 주었고, 처음 시작점을 방문 체크한 뒤

큐에 좌표와 cnt를 넣어준다.

큐가 빌 때까지 반복하며 큐에서 값을 하나 빼서 저장하고, 만약 현재 빼 온값의 cnt가 최댓값 갱신 중인

ans 보다 클 경우 ans를 변경하여 주고, 사방 탐색으로 하면서 범위를 벗어나거나

이미 방문했거나 육지가 아닌 경우 다시 다음으로 넘어가고 그렇지 않은 경우에 대해서만

방문 체크와 큐에 좌표를 담고 cnt를 기존 값 +1 해서 담아주는 방식으로 문제를 해결했다.