(JAVA) 백준 2842번 : 집배원 한상덕 --- [BFS, 투 포인터]

www.acmicpc.net/problem/2842 

2842번: 집배원 한상덕

 

안녕하세요.

 

BFS와 투 포인터를 사용하여 문제를 해결했습니다.

사실 풀다가 도저히 모르겠어서 해설을 참고했습니다...

 

물론, 투포인터 사용하지 않고 DFS와 이분탐색으로 해결하신 분들도 있더라구요.

 

그치만 제가 풀어본 방법으로 포스팅하겠습니다!

 

 

 

짚어볼 사항

---

  -  상덕이가 느낀 피로도 = 방문 지점 중 피로도 최댓값 - 최솟값. 

이 값이 최소가 되는 경우의 최소값을 구해야 합니다.

 

즉, 전체 이동거리를 구하는 것처럼 가중치를 활용하는 문제가 아니기 때문에(실제로 가중치도 없음) 최소값이라고해서 다익스트라 같은 알고리즘을 사용하면 안되고, BFS / DFS 를 사용하여 가중치 없는 그래프의 경로를 탐색해야 합니다.

 

그렇기 때문에, 피로도 확인을 위해 특정 지점에 방문할 때 마다 현재까지 방문한 지점들 중 최댓값, 최솟값과 비교하며 갱신하는 작업이 필요합니다.

 

 

여기서!!!

 

저는 투 포인터 방법을 이용해서 구했는데요.

 

  1)  모든 지점의 피로도 값을 배열로 만들고 오름차순 정렬을 해둡니다.

  2)  start, end 포인트를 만드는데, 이를 각각 최솟값 / 최댓값 으로 가정합니다.

  3)  모든 가능한 경우를 따질 때, start 포인트의 피로도 값 > 현재 지점의 피로도 값 || end 포인트의 피로도 값 < 현재 지점의 피로도 값은 따지지 않았습니다.

즉, start 포인트의 피로도 값 <= 현재 지점의 피로도 값 <= end 포인트의 피로도 값 인 경우에만 Queue에 넣고 BFS를 계속 진행했습니다.

 

 

 

그래서 만약 K지점을 전부 방문한 경우가 없다!!! 싶으면 end 포인트를 +1

K지점을 모두 방문한 경우가 있다!!! 싶으면 상덕이가 느낀 피로도 갱신해주고, start 포인트를 +1

 

이렇게 end포인트가 배열의 끝에 도달할 때 까지 반복 진행합니다.

또는, start 포인트가 end 포인트보다 앞서기 전까지도 말이죠!

 

 

 

  -  P지점에서 시작하여 무조건 K지점은 전부 방문해서 다시 P지점으로 돌아와야 합니다.

저는 여기서 많이 어려움을 느꼈었습니다. K지점 방문 여부는 어떻게 판단하지? 경로를 추적해야하나?

 

그래서 저는 처음에 방문할 때 마다 'K' 인지 아닌지 체크해서 K방문 개수를 카운팅했습니다.

그러고 P지점일 때는, K방문 개수와 비교해서 개수랑 다르면 

 

너이자식! K지점 전부 안가봤구나! 하고 바로 이 경로는 탈락시키는 것이죠.

 

 

  -  boolean 2차원 배열로 지점 방문 체크했습니다. 방문 체크를 하지 않으면 무한 사이클 돕니다.

 

 

 

이 것들만 유의하여 푸신다면, 해결하실 수 있다고 생각합니다!

 

맨 하단에 소스코드 있습니다.

이상입니다.

 

 

감사합니다!

 

소스코드

---