프로그래머스 문제 풀이 섬 연결하기

문제 URL 섬 연결하기

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이 문제는 결론부터 말하면 "가중치 그래프에서 최소 신장 트리(이하 'MST')"를 만드는 문제입니다. 가중치가 있는 그래프에서 최소 신장 트리를 만드는 방법은 크게 2가지가 있습니다.

 

1. 프림 알고리즘
2. 크루스칼 알고리즘

저는 여기서 "크루스칼 알고리즘"을 통해서 가중치 그래프를 MST로 만들 것입니다. MST와 크루스칼 알고리즘의 자세한 설명은 다음을 참고하세요.

 

• MST와 크루스칼 알고리즘

먼저, 문제의 입력을 통해서 그래프를 만들어야 합니다. 문제의 예제를 기준으로 만들어보겠습니다.

 

입력:
n = 4
costs = [ [0,1,1], [0,2,2], [1,2,5], [1,3,1], [2,3,8] ]

 

문제에 따르면, 정점은 0, 1, 2, 3으로 총 4개입니다. 이를 기준으로 4x4 그래프를 만들어줍니다.

 

graph = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]

 

이제 costs를 기준으로, 그래프에 가중치를 매겨줍니다. costs는 (정점1, 정점2, 가중치)의 배열이므로 이를 순회하여 graph를 초기화시켜줍니다.

 

graph = [
    [0, 1, 2, 0],
    [1, 0, 5, 1],
    [2, 5, 0, 8],
    [0, 1, 8, 0]
]

 

이렇게 하면, 가중치 그래프의 초기화는 끝났습니다. 이제 크루스칼 알고리즘을 통해서, 가중치 그래프를 MST로 만들면 됩니다. 먼저, 손쉽게 표현하기 위해서, costs를 edges로 바꾸겠습니다. edges는 (가중치, 정점1, 정점2) 형태의 리스트입니다.

 

edges = [(1, 0, 1), (2, 0, 2), (5, 1, 2), (1, 1, 3), (8, 2, 3)]

 

이제 크루스칼 알고리즘을 사용하여, MST로 만들겠습니다. 크루스칼 알고리즘은 edges를 가중치 기준으로 역순으로 우선순위 큐에 집어넣습니다. 그리고, 가중치가 큰 edge부터 다음을 실행해봅니다.

 

1. 그래프에서 edge를 먼저 빼봅니다.
2. 그래프가 edge없이도, 연결이 되어 있는지 확인합니다.
3. 연결되어 있지 않다면, 다시 edge를 복원합니다.

이 과정을 edge의 개수가 n개보다 작아질때까지, 반복합니다. 즉, 연결된 edge의 개수가 그래프의 정점 vertex의 개수보다 1개 적어질 때까지 반복하면 됩니다. 이를 파이썬으로 코드로 나타내면 다음과 같습니다.

 

def is_connect_without_edge(n, graph, is_visit, here, dest):
    # 기저 사례1. 이미 방문한 지점이라면 False 반환
    if is_visit[here]:
        return False
    # 기저 사례2. 목적지 dest에 도착하면 True 반환 (edge없이도, 그래프는 연결되어 있습니다.)
    if here == dest:
        return True
    
    res = False
    # 1. 현재 지점 방문합니다.
    is_visit[here] = True
    
    # 2. 현재 지점과 연결되어 있고, 방문하지 않은 지점을 방문한 후, 연결되어있는지 확인합니다.
    for to in range(n):
        if graph[here][to] > 0 and is_visit[to] == False:
            res |= is_connect_without_edge(n, graph, is_visit, to, dest)
    
    return res
    
    
def kruskal(n, edges, graph):
    import heapq
    # 1. 우선순위 큐 생성합니다.
    pq = []
    # 2. edge 개수를 세는 edgeCnt를 생성합니다.
    edgeCnt = 0
    # 3. edges를 기준으로 가중치 역순으로 pq에 저장합니다.
    for edge in edges:
        (w, v, u) = edge
        heapq.heappush(pq, (-w, v, u))
        edgeCnt += 1
    # 4. 연결된 edge의 개수 edgeCnt가 정접의 개수보다 1개 적어질 때까지 다음을 반복합니다. (edgeCnt >= n)
    while edgeCnt >= n:
        # 1. 우선순위 큐에서, edge를 뺴옵니다.
        (w, v, u) = heapq.heappop(pq)
        # 2. 그래프에서 edge를 제거합니다.
        graph[v][u] = 0
        graph[u][v] = 0
        edgeCnt -= 1
        is_visit = [False] * n
        
        # 3. 해당 edge를 지워도 연결되는지 확인합니다. 만약, 연결이 끊어진다면, edge를 복원합니다.
        if is_connect_without_edge(n, graph, is_visit, v, u) == False:
            graph[v][u] = -w
            graph[u][v] = -w
            edgeCnt += 1

 

크루스칼 알고리즘을 거친 MST는 다음과 같습니다.

 

graph(MST) = [
    [0, 1, 2, 0],
    [1, 0, 0, 1],
    [2, 0, 0, 0],
    [0, 1, 0, 0]
]

 

정점 0은 정점1, 정점 2랑 연결되어 있고, 정점 1은 정점 0과 정점 3, 정점 2는 정점 0, 정점 3은 정점 1에 연결되어 있습니다. 즉, 문제 설명에 나온 그림으로 MST가 만들어지게 됩니다. 이제 이 MST를 DFS 알고리즘을 통해서 모든 정점에 방문합니다. 그리고 방문할 때마다, 가중치 cost를 더해주면 됩니다. DFS 알고리즘을 코드로 표현하면 다음과 같습니다.

 

def dfs(n, graph, is_visit, here):
    # 기저 사례1. 이미 방문한 지점은 세지 않습니다. 0을 반환합니다.
    if is_visit[here] == True:
        return 0
    
    # 1. 현재 지점 here를 방문합니다.
    is_visit[here] = True
    res = 0
    
    # 2. here와 연결되어 있고, 방문하지 않은 지점 there를 찾습니다. 이 때 가중치를 더해주고, 그 지점에서 구하는 가중치들도 더해줍니다.
    for there in range(n):
        if graph[here][there] > 0 and is_visit[there] == False:
            res += graph[here][there] 
            res += dfs(n, graph, is_visit, there)
    
    # 3. 해당 지점의 가중치를 반환합니다.
    return res

 

이렇게 하면, 문제의 답을 구할 수 있습니다. 정확성 테스트만 있기 때문에, 이 정도면 충분히 훌륭한 문제 풀이라고 할 수 있겠습니다.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. 입력을 통해서 graph를 만듭니다.
2. 크루스칼 알고리즘을 통해서, graph를 MST로 만듭니다.
3. DFS를 통해서 MST를 순회하여 그 비용들을 구합니다.

다음을 코드로 나타내면 다음과 같습니다. 먼저 PYTHON 코드입니다.

 

PYTHON 코드

def is_connect_without_edge(n, graph, is_visit, here, dest):
    """here 지점에서 dest까지, 연결되는지 확인하는 함수입니다."""
    if is_visit[here]:
        return False
    
    if here == dest:
        return True
    
    res = False
    is_visit[here] = True
    
    for to in range(n):
        if graph[here][to] > 0 and is_visit[to] == False:
            res |= is_connect_without_edge(n, graph, is_visit, to, dest)
    
    return res
    
    
def kruskal(n, edges, graph):
    """크루스칼 알고리즘을 통해서 graph를 mst로 만듭니다."""
    import heapq
    
    pq = []
    edgeCnt = 0
    
    for edge in edges:
        (w, v, u) = edge
        heapq.heappush(pq, (-w, v, u))
        edgeCnt += 1
    
    while edgeCnt >= n:
        (w, v, u) = heapq.heappop(pq)
        graph[v][u] = 0
        graph[u][v] = 0
        edgeCnt -= 1
        is_visit = [False] * n
        
        if is_connect_without_edge(n, graph, is_visit, v, u) == False:
            graph[v][u] = -w
            graph[u][v] = -w
            edgeCnt += 1

            
def dfs(n, graph, is_visit, here):
    """dfs를 통해서 mst를 순회합니다. 순회할 때, 그 비용들을 더합니다."""
    if is_visit[here] == True:
        return 0
    
    is_visit[here] = True
    res = 0
    
    for there in range(n):
        if graph[here][there] > 0 and is_visit[there] == False:
            res += graph[here][there] 
            res += dfs(n, graph, is_visit, there)
    
    return res


def solution(n, costs):
    # 1. 입력을 통해서 graph를 만듭니다.
    edges = [ (w, v, u) for (v, u, w) in costs ]
    graph = [ [0] * n for _ in range(n) ]
    
    for (w, v, u) in edges:
        graph[v][u] = w
        graph[u][v] = w
    
    # 2. 크루스칼 알고리즘을 통해서 graph를 MST로 만듭니다.
    kruskal(n, edges, graph)

    # 3. DFS를 통해서 모든 지점을 순회하는 비용을 구합니다.
    is_visit = [False] * n
    answer = dfs(n, graph, is_visit, 0)
    return answer

 

다음은 CPP 코드입니다. 알고리즘은 동일합니다. 다만, CPP는 파이썬처럼 구조 분해 기능이 없기 때문에, Edge라는 구조체를 따로 선언하였습니다.

 

CPP 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef struct edge {
    int v;
    int u;
    int w;
} Edge;

bool operator < (Edge e1, Edge e2) {
    return e1.w < e2.w;
}

bool is_connect_without_edge(const int n, const vector< vector<int>> & graph, vector<bool> & is_visit, int here, int dest) {
    if (is_visit[here]) {
        return false;
    }
    
    if (here == dest) {
        return true;
    }
    
    bool res = false;
    is_visit[here] = true;
    
    for (int to=0; to<n; to++) {
        if (graph[here][to] > 0 && !is_visit[to]) {
            res |= is_connect_without_edge(n, graph, is_visit, to, dest);
        }
    }
    
    return res;
}

void kruskal(const int n, const vector< vector<int>> & costs, vector< vector<int>> & graph) {
    priority_queue<Edge, vector<Edge>, less<Edge>> pq;
    int edgeCnt = 0;
    
    for (const auto & cost : costs) {
        Edge edge = { cost[0], cost[1], cost[2] };
        pq.push(edge);
        edgeCnt += 1;
    }
    
    while (edgeCnt >= n) {
        Edge edge = pq.top();
        pq.pop();
        graph[edge.v][edge.u] = 0;
        graph[edge.u][edge.v] = 0;
        edgeCnt -= 1;
        auto is_visit = vector<bool>(n, false);
        
        if (!is_connect_without_edge(n, graph, is_visit, edge.v, edge.u)) {
            graph[edge.v][edge.u] = edge.w;
            graph[edge.u][edge.v] = edge.w;
            edgeCnt += 1;
        }
    }
}

int dfs(const int n, const vector< vector<int>> & graph, vector<bool> is_visit, int here) {
    if (is_visit[here]) {
        return 0;
    }
    
    int res = 0;
    is_visit[here] = true;
    
    for (int there = 0; there<n; there++) {
        if (graph[here][there] > 0 && !is_visit[there]) {
            res += graph[here][there];
            res += dfs(n, graph, is_visit, there);
        }
    }
    
    return res;
}

int solution(int n, vector<vector<int>> costs) {
    auto graph = vector<vector<int>>(n, vector<int>(n, 0));
    
    for (const auto & cost : costs) {
        graph[cost[0]][cost[1]] = cost[2];
        graph[cost[1]][cost[0]] = cost[2];
    }
    
    kruskal(n, costs, graph);
    auto is_visit = vector<bool>(n, false);
    int answer = dfs(n, graph, is_visit, 0);
    return answer;
}

 

이번 문제는 그래프, DFS, MST, 크루스칼 알고리즘을 모두 알고 있어야 해결이 가능합니다. 이 중 크루스칼 알고리즘은 "가중치가 큰 edge를 빼다보면, 가장 적은 비용으로 연결되는 최소 신장 트리를 만들 수 있다"라는 탐욕법을 적용한 것입니다.

 

다른 분들은 DisjointSet을 이용하여 크루스칼 알고리즘을 표현하였는데, 저는 제가 설명했던 MST와 크루스칼 알고리즘의 내용을 충실히 따랐습니다.