[프로그래머스][LEVEL3] 섬 연결하기

# 문제 원문

https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n / costs / return

4

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

4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

 

# 문제 풀이

 

입력 받은 n개의 섬을 입력 받은 costs를 참고하여서 가장 적은 비용으로 모두 연결하는 비용을 구해서 반환하는 문제이다. 그리디 관련이며 코스트 기준으로 오름차순 정렬하여서 연결 되지 않은 부분들이 있을시 연결해주면서 그 코스트를 합하면 된다. 문제의 함정이 있다면 하나의 그룹만 주어지지 않아서 n개의 그룹이 생길 경우 그 그룹들을 연결해줘야한다는 점 정도이다. 개인적으로 그리디와 함수 체이닝 만을 통해서 풀어보려고 했는데 dfs 방식으로 코드를 짜는 것 보다 코드가 별로다. 그리디라고 해서 dfs 방식 사용을 금하지는 않으니 앞으로는 괜히 쓸데 없이 특정 스타일을 고집하지 말자. 

 

# 솔루션 플로우

1. 입력 받은 n길의의 visited 배열을 만든다.

2. 입력받은 costs의 cost를 기준으로 정렬한다.

3. costs를 순회한다.

4. 해당 섬에 방문하지 않은 경우나 서로 다른 그룹에 속한 섬들을 서로 연결해준다.(cost 추가)

5. 모든 섬을 연결하는 가장 적은 cost 총합을 구한다.

6. 구해진 result를 반환한다.

1. 그리디

function solution(n, costs) {
    const visited = new Array(n).fill(false);

    return costs
        .sort((a, b) => a[2] - b[2])
        .reduce((result, current) => {
            const [x, y, cost] = current;
            if (visited[x] + visited[y] === 0 || visited[x] !== visited[y]) {
                result.cost += cost;

                if (!visited[x] && !visited[y]) {
                    visited[x] = result.group;
                    visited[y] = result.group;
                    result.group++;
                } else {
                    if (visited[x] && visited[y]) {
                        const group = visited[y];
                        visited.forEach((current, idx) => {
                            if (current === group) visited[idx] = visited[x];
                        });
                    } else {
                        visited[x] ?
                            visited[y] = visited[x] :
                            visited[x] = visited[y];
                    }
                }
            }

            return result;
        }, { cost: 0, group: 1 }).cost;
}