프로그래머스 50일차 - 섬 연결하기

오늘까지 그리디를 풀고 내일부터는 스택 큐를 풀 생각이다.

 

자료는 https://www.youtube.com/watch?v=_IZuE7NIeW4 해당 영상이며,

백준 문제이므로 추가적으로 풀려면 위 문제를 풀어보면 된다.

나는 프로그래머스 문제만 풀려고 한다.(나중에는 Leetcode 풀어야지)

 

---

해설

 

문제의 요점은 최소한 섬 1개씩은 다 돌아야하고, 그 섬의 cost가 제일 적어야한다 이다.

 

따라서 해결방안은

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]에서

1,2,2,3,3 인 [1]번째 인덱스들 중에서 중복값인 것인 [2]번째 인덱스끼리 비교해서 값이 작은 것들을 찾으라는 말이다.

 

그럼 1, 2, 1이 나온다.

참고로 n개의 모서리를 다 돌려면 n-1번 만큼만 이동할 수 있으면 최소한으로 n개 모서리를 다 돌 수 있다.

 

그래서 이처럼 dictionary를 만들고

중복되는 키가 있으면 작은 값만 넣도록 하고,

중복되는 키가 없으면 값을 그냥 넣게 해서

딕셔너리 요소의 값을 모두 더했다.

 

그랬더니 테스트에서 실패했다.

 

다른 사람 풀이를 봤다.

Kruskal 알고리즘으로 최소 비용 경로를 찾는 것이 있었다.

 

우선 lambda를 사용해서 cost를 기준으로 오름 차순을 한다.

이 이유는 for문을 돌리는데 작은 cost 기준으로 먼저 넣어버리니까 cost 큰 값은

if v[0] in link and v[1] in link에서 걸러진다.

효율적인 방법이다.

 

그리고 link = set([costs[0][0]]) 

이 부분은 중복값을 없애려는 게 아니고 값 초기화 및 밑에 튜플 값에 update를 하려고 사용한거다.

값을 수정하기 위함이라는 거다. 

 

while len(link) != n: 여기는 연결할 수 없는 섬은 주어지지 않습니다 위함이다.

섬의 개수가 같아지는 순간 종료 된다.

왜냐하면 처음에 1개를 넣었고, 연결하는 최소 숫자는 n-1이다.

1개 + n-1 개 투입하면 n개로 while문이 종료가 된다.

 

if v[0] in link and v[1] in link:

• 두 섬이 이미 더 낮은 가격으로 연결이 되었을 경우 추가 적인 데이터 무시할 수 있음

if v[0] in link or v[1] in link:

• 두 섬 중 하나가 연결이 되어있지 않을 때 비용을 더하기

link.update([v[0], v[1]])

• set.update()는 중복을 제거
• 이미 섬이 연결되었을경우 중복된 섬은 추가되지 않고 최대 n 개의 섬을 유지

이렇게 총 cost를 리턴한다.

 

---

내가 했던 오류는 1번째 인덱스인 연결되는 섬만 찾았기 때문이다.

0과 1을 모두 체크하면서 코스트를 계산했어야했다.

 

문제 푸는 방향은 맞았는데 디테일이 부족했다.