Number of Operations to Make Network Connected(leetcode, 1319)

문제 설명

노드의 개수 n과 edge가 주어졌을 때, 해당 edge를 이요해서 모든 노드를 연결하는 횟수를 구하는 문제다.

문제만 보면 엄청... 복잡할 거 같지만 실제로는 굉장히 쉬운 문제다.

문제 풀이

첫 번째 접근

처음에는 사이클을 찾아서 중복되는 edge를 하나씩 옮겨줘야 한다고 생각했다. 그냥 문제가 말한 그대로 구현하려 한 것이다. 그러나 이렇게 하면 풀이가 너무 복잡해지고 현재 내 실력으로는 접근할 수 없었다. 그래서 union find를 이용해야 하나? 이것저것 찾아봤으나 도저히 모르겠다 싶었다.

두 번째 접근

다른 사람의 풀이를 보니 엄청 간단한 문제였다. 이런 단순하게 생각해서 모든 노드를 연결하기 위해서는 적어도 노드의 개수-1 만큼의 edge가 필요하다.

만일 위의 조건을 만족한다면 떨어져 있는 노드의 개수를 구하면 그게 답이다.

예를 들어 총 노드의 개수는 6, edge의 개수는 5, 떨어져 있는 노드는 2개라고 해보자. 그러면 5개의 edge가 노드 4개와 연결되어 있다는 의미이다. 그렴 5개의 노드 중 2개를 떼서 떨어져 있는 노드 2개에 연결해주면 모든 노드가 연결이 된다.

여기서 무슨 edge를 옮겨줘야 하고 어쩌고 이건 생각할 필요가 없다. 왜냐하면 우리는 동떨어진 노드의 개수만을 생각하기 때문이다.

문제에서는 연결하는 횟수를 구하라는데 왜 동떨어진 노드의 개수를 구하라는 거지? 의문이 들 수 있다. 이것 또한 쉽게 이해할 수 있는데 노드 하나를 연결 할 때마다 횟수가 하나씩 늘기 때문이다. 즉, 동떨어진 노드 2개를 연결하고 싶다면 총 횟수가 2가 되는 것이다.

동떨어진 노드는 깊이 우선 탐색을 이용해서 구할 수 있다. 깊이 우선 탐색이로 연결된 노드를 옮겨가고 옮겨가는데, 만일 방문하지 않는 노드가 있다면 이는 동떨어진 노드라는 뜻이다. 이때는 동떨어진 노드를 연결해줬다는 의미로 정답을 하나 올려주면 된다.

다만, 처음에는 당연히 방문하지 않았기에 첫 노드가 다른 노드와 연결되어 있어도 정답을 1 올려준다. 이때는 반환할 때 1을 빼주거나 반복문을 돌기 전에 미리 첫 노드를 방문했다고 표시하면 된다.

코드

Java

import java.util.*;
import java.io.*;

//문제를 곧이 곧대로 본다면 어렵게 느껴지겠지만, 이 문제는 연결되지 않는 노드를 찾는 문제다.
class Solution {

    public static List<ArrayList<Integer>> graph;
    public static boolean[] visit;

    public int makeConnected(int n, int[][] connections) {

        //edge가 노드의 수 - 1보다 작다면 이는 모든 노드를 연결 할 수 없기에 return -1을 한다.
        if(connections.length < n-1){
            return -1;
        }

        graph = new ArrayList<>();
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<>());
        }

        //주어진 노드 연결
        for(int[] connection : connections){
            int a = connection[0];
            int b = connection[1];

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        visit = new boolean[n];
        int answer = 0;

        //만일 해당 노드를 방문하지 않았다면 answer에다가 1을 더해준다.
        //해당 노드를 방문하지 않았다는 것은 해당 노드가 동떨어져 있다는 의미이다.
        //그러므로 정답을 추가해 줘야 함(시작 부분은 예외 이건 반환할 때 -1을 빼줘서 조정한다.)
        for(int i=0; i<n; i++){
            if(visit[i] == false){               
                answer++;
                visit[i] = true;
                dfs(i);
            }
        }

        return answer - 1;
    }

    public void dfs(int node){

        //해당 노드의 이웃 노드를 방문하지 않았다면 이웃 노드를 방문하고 그 노드로 옮겨 간다.
        for(int neighbor : graph.get(node)){
            if(visit[neighbor] == false){
                visit[neighbor] = true;
                dfs(neighbor);
            }
        }
    }
}

Python

class Solution:

    def makeConnected(self, n: int, connections: List[List[int]]) -> int:

        if len(connections) < n-1:
            return -1

        graph = [[] for _ in range(n)]
        visit = [False for _ in range(n)]
        answer = 0

        for connection in connections:
            a = connection[0]
            b = connection[1]

            graph[a].append(b)
            graph[b].append(a)

        # bfs를 앞에 써줘야지 파이썬이 참조할 수 있다.
        def bfs(node):
            for neighbor in graph[node]:
                if visit[neighbor] == False:
                    visit[neighbor] = True
                    bfs(neighbor)
        

        for i in range(n):
            if visit[i] == False:
                answer = answer + 1
                visit[i] = True
                bfs(i)



        
        return answer - 1