(JAVA) 백준 2589번 : 보물섬

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

2589번: 보물섬

 

 

시간을 너무 오래 잡아먹은 문제입니다.

 

BFS와 DFS를 활용해야 합니다...

 

 

제가 푼 것보다 등수가 높으신 분의 코드를 보고

 

그 분의 알고리즘 방식이 훨씬 효율적이고 좋다고 생각해서

 

그 분의 알고리즘과 제 코드를 적절히 섞어서 설명드리겠습니다.

 

매커니즘

---

우선 문제를 보면

 

 

 

"L" 이 붙어있는 지역 내에서 임의의 두 곳을 선택하고, 두 곳 사이의 최단 거리들 중 가장 큰 값을 구해야 한다.

 

이 때 저는 (0, 0) 부터 끝까지 하나씩 BFS로 다른 점들까지의 거리를 찾았고(이 때 int 2차원 배열 사용), 이 값들 중 가장 큰 값을 정답으로 삼았습니다만,

 

메모리 크기가 엄청나게 크고, 실행 시간 또한 기준보다 두 세배는 높았습니다.

 

 

 

제출 후 굇수님의 코드 분석을 해보니 저와 다른 점이 몇 가지 존재했습니다.

 

1) 인접한 'L' 로만 묶인 지역 내에서 이동 가능한 방향이 1개 또는 2개인 좌표를 각각의 ArrayList에 저장.

 

2) 우선순위인 이동 가능 방향 1개인 지점이 하나라도 있으면 그 지점들만 BFS 진행.

만약 하나도 없으면 2개인 지점들을 하나씩 BFS 진행해서 최단 거리 구하기.

 

3) 좌표를 나타내는 클래스 내에 Time 변수 넣어서 BFS 진행

 

인데요.

 

간단한 매커니즘 순서

---

 

1) 입력 값을 바탕으로 2차원 배열 map 생성

 

2) map을 탐색하며 이동 가능한 방향 체크 후 ArrayList에 저장

 

3) 저장된 ArrayList의 좌표 값에서 BFS 시작

 

4) 최단 거리 출력

 

 

입니다.

감사합니다.

 

굇수님의 코드 보러 가기

 

 

소스코드

---