-
https://www.acmicpc.net/problem/2589
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202589
해당 문제는 map가 주어졌을 때 육지에서 갈 수 있는 최단거리 중 가장 먼 두지점에 보물이 묻혀있다고 할 때
가장 먼 두지점의 거리를 구하는 문제다.
처음 문제를 보고 육지를 방문하면 bfs 한번 돌려서 가장 먼 지점에서 다시 bfs를 돌려서 길이를 갱신하면 되겠다고
생각하고 문제를 보다가 범위가 별로 안 커서 그냥 각 칸마다 bfs를 돌려서 최대 거리를 갱신하는 방식으로
문제를 해결했다.
먼저 입력 처리를 해준 뒤, 육지인 칸에 대해서 bfs를 모두 돌려준다.
각 육지마다 방문 배열을 초기화해줘야 하기 때문에 bfs안에 선언해 주었고, 처음 시작점을 방문 체크한 뒤
큐에 좌표와 cnt를 넣어준다.
큐가 빌 때까지 반복하며 큐에서 값을 하나 빼서 저장하고, 만약 현재 빼 온값의 cnt가 최댓값 갱신 중인
ans 보다 클 경우 ans를 변경하여 주고, 사방 탐색으로 하면서 범위를 벗어나거나
이미 방문했거나 육지가 아닌 경우 다시 다음으로 넘어가고 그렇지 않은 경우에 대해서만
방문 체크와 큐에 좌표를 담고 cnt를 기존 값 +1 해서 담아주는 방식으로 문제를 해결했다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 20291 파일 정리 JAVA (0) 2021.12.24 Baekjoon 1269 대칭 차집합 JAVA (0) 2021.12.16 Baekjoon 12761 돌다리 JAVA (0) 2021.12.13 Baekjoon 18405 경쟁적 전염 JAVA (0) 2021.12.11 Baekjoon 2470 두 용액 JAVA (0) 2021.12.11 댓글