최소신장트리. [17472]

[1. 문제 설명]

문제가 조금 길어서 생략

---

[2. 풀이 접근]

== 풀이 개요 == 

1. 인접한 땅들에 공통의 번호를 부여. (== 정점의 번호를 부여)
2. 정점 간 최소 거리를 계산. (최소 거리는 2 이상이어야 한다.)
3. MST 를 생성해본다.
4. MST 생성 여부로 출력 할 답을 결정한다. (== 모든 정점이 MST 에 포함되었는 가?)

 

== 단계 1 ==

• 먼저 입력으로 주어진 이차원 배열을 순회
• 값이 1 인 경우 해당 위치를 기준으로 상하좌우로 이동하면서 값이 1인 위치에 노드 번호를 부여
  => (dfs 로 탐색)
• 노드 번호는 2부터 시작해야 한다.
  => 원래 값이 1인 것과 구분이 되지 않는다.

 

== 단계 2 ==

• 정점 번호가 할당 된 이차월 배열을 순회
• 정점 번호가 할당 된 곳을 발견 했을 시
• 정점 번호를 만날 때 까지, 상하좌우로 계속 이동하면서 마지막 위치 갱신
• 위에서 구한 위치와 최초 위치 간의 거리를 계산
  => 좌표 간 거리 계산 시, 좌표 변화량 (절대값) 을 먼저 구하고 1을 빼야 한다.
• 위에서 구한 거리가 2 이상인 경우 만 from -> to 로 가는 edge 의 거리를 최소값으로 갱신
  => 문제에서 섬 간의 거리는 2 이상이 되어야 한다고 명시

 

== 단계 3 == 

• 단계 2 를 거치면 모든 정점 간 최소 거리가 구해져 있다.
  => 특정 섬 들 간 연결되어 있지 않을 수 있다. 
  => 그러나 데이터 적으로는 maxint 값이 설정되므로, 사용하지 않도록 주의해야 한다.
• 크루스칼 알고리즘을 이용하여 MST 를 생성하여 최소 비용을 계산한다.

 

== 단계 4 ==

• 모든 정점이 같은 집합에 속해있으면 MST 생성 성공이므로 최소 비용 반환
• 그렇지 않다면 -1을 반환

---

[3. 코드]