프로그래머스 문제 - 네트워크

프로그래머스 네트워크 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

200개 이하의 컴퓨터가 주어지며 각 컴퓨터는 0부터 N-1인 정수로 표현됩니다.
n번째의 연결정보가 차례대로 주어지는데 0은 연결안됨, 1은 연결됨을 표현합니다.
연결된 컴퓨터끼리는 하나의 네트워크로 연결이 가능합니다.
모든 컴퓨터가 네트워크 연결이 되기 위한 최소한의 네트워크 수를 구해야합니다.

문제 풀이

컴퓨터들의 연결을 알아내면 되기 때문에 Union-find를 사용하여 모든 컴퓨터의 연결을 확인합니다.

for(int i = 0; i < computers.size(); i++)
    {
        for(int j = 0; j < computers[i].size(); j++)
        {
            //컴퓨터와 연결된 부분을 찾아 배열로 표현
            if(computers[i][j] == 1)
            {
                int bigTemp, smallTemp;
                if(check[i] < check[j])
                {
                    bigTemp = check[j];
                    smallTemp = check[i];
                }
                else
                {
                    bigTemp = check[i];
                    smallTemp = check[j];
                }
                for(int k = 0; k < n; k++)
                {
                    if(check[k] == bigTemp)
                    {
                        check[k] = smallTemp;
                    }
                }
            }
        }
    }

이후에 나온 배열을 set 배열에 넣어주면 중복된 숫자들을 제거한 수만 들어가게 되며 set 배열의 크기가 네트워크의 최소값이 됩니다.

전체 코드

이번 문제는 union-find를 사용하면 풀 수 있는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    int check[200];
    
    for(int i = 0; i < n; i++)
    {
        check[i] = i;
    }
    
    for(int i = 0; i < computers.size(); i++)
    {
        for(int j = 0; j < computers[i].size(); j++)
        {
            //컴퓨터와 연결된 부분을 찾아 배열로 표현
            if(computers[i][j] == 1)
            {
                int bigTemp, smallTemp;
                if(check[i] < check[j])
                {
                    bigTemp = check[j];
                    smallTemp = check[i];
                }
                else
                {
                    bigTemp = check[i];
                    smallTemp = check[j];
                }
                for(int k = 0; k < n; k++)
                {
                    if(check[k] == bigTemp)
                    {
                        check[k] = smallTemp;
                    }
                }
            }
        }
    }
    
    //set을 사용해 중복되는 수를 없애줌
    set<int> s;
    for(int i = 0; i < n; i++)
    {
        s.emplace(check[i]);
    }
    answer = s.size();
    
    return answer;
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/43162