[자바] 프로그래머스 - 지형 이동 [코딩테스트 연습 Lv4]

- 문제 : https://programmers.co.kr/learn/courses/30/lessons/62050

- 코드 : https://github.com/NaHwaSa/Programmers_OnlineJudge/blob/main/Level%204/%EC%A7%80%ED%98%95%20%EC%9D%B4%EB%8F%99.java

 

1. 모든 칸을 방문한다고 했지, 한 칸에 여러번 가면 안된다는 말은 없었다. 따라서 높이차이가 height 이하인 곳은 가중치 0으로, 아무런 제약 없이 돌아다닐 수 있다.
-> 다시 말해, 상하좌우로 높이차이가 height 이하인 곳은 서로 그룹으로 생각해도 됨.
-> 예를들어 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]]에 height=3인 경우 위 2개의 행인 1,4,8,10,5,5,5,5 높이인 부분 (문제상 노란색으로 칠해진 부분)이 그룹 A이고 3,4 행 중 20높이인 곳을 뺀 부분이 그룹 B (문제상 파란색), 마지막 20 높이인 곳을 그룹 C 라 생각해볼 수 있음.

2. 2차원 지도 형태에서 연산의 편의를 위해 그래프로 변경했다. 2차원에서 1차원으로 변경할 것이므로 좌표를 하나의 숫자로 표현 가능해야 하고 그걸 위한 함수가 35line의 getGroupIdx() 이다.

3. 그룹짓는것은 union - find를 이용했다. (51~56line)
   -> 이를 통해 '1'의 예시처럼 A, B, C 그룹이 나오게 됨.
   -> 56 line 이후부터 나오는 a, b와 Node의 a, b는 모두 이 그룹명을 뜻하게 됨. 실제로 위처럼 돌리면 A=7, B=14, C=15 가 나옴. (해당 번호는 그룹을 대표하는 번호로, '2'에서 계산된 번호임. 각 좌표마다 서로 다르게만 나오면 뭐가 나오든 상관 없으므로 숫자 자체에 의미가 있진 않음)

4. 이후 그룹번호를 기준으로 서로간에 가장 작은 높이차이로 지나갈 수 있는 위치를 찾아야하는데, 그 부분이 59 ~73 line임.

  위처럼 진행하면 근데 edge 리스트는 예시를 기준으로 (A,B,5), (A,B,5), (A,B,5), (A,B,5), (B,C,10), (B,C,10) 이렇게 중복된 값이 포함된 6개가 들어가게 됨.
   실제로 필요한건 (A,B,5), (B,C,10)의 두가지인데 이렇게 둔 이유는, 어차피 정렬을 통해 그리디 기법으로 최소 간선을 찾아나갈 것이고, 이미 연결된 그룹은 무시할 것이므로 상관이 없어서 그러함. 
   참고로 위 예시는 저런식이지만 실제로는 (A,B,1), (A,B,3), (A,B,5) 이렇게 있다면 (A,B,1)만 써야됨. (높이차가 최소인 것)
  

 위를 중복 없이 처리하려면 HashSet을 써서 A,B의 중복쌍일 경우 최소값만 넣도록 하고, KeySet을 다시 빼서 정렬하는 과정이 들어가야하는데,
   어차피 최악의 경우라도 9만개밖에 안되므로 그냥 다 냅두고 정렬해버리는게 더 편함.

5. MST (Minimum Spanning Tree - 최소 신장 트리)를 구하는 방법 중 크루스칼 알고리즘을 활용하기 위해 간선을 정렬하고, 최소 간선을 그리디하게 연결하면서 서로 그루핑해버림.
   그럼 처음에 (A,B,5)가 뜰테니 A-B가 연결되서 그냥 A그룹이 되고, 이후 A-B 사이의 연산은 88 line에서 막혀서 무시됨.
   그다음 (B,C,10)이 나올텐데 find(B) = A (그루핑 되었으므로)가 될테니 A-C도 결국 연결되게 됨. 이 과정에서 서로 다른 그룹이 나올때마다 sum을 더해줌.
   MST 구하면서 전체를 방문했냐로 판단해도 될텐데 그루핑 하면서 진행하는 이유는, MST 에서 싸이클이 생기면 안되기 때문에 그걸 체크하기 위해서임. (그룹이 생기면 싸이클이 생긴 것)