프로그래머스 : 네트워크 C++ (유니온 파인드 연습)

 

 

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

풀이 및 후기

1. computers 배열 다 돌고 후에 꼭 한번 더 parent 초기화를 해줘야된다!!!!

2. 이거때문에 TC 9번에서 계속틀림 사실 이유는 잘 모르겠다

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int parent[201];

int getParent(int x)
{
    if(parent[x]==x)
        return x;
    
    return parent[x] = getParent(parent[x]);
}

void connect(int a,int b)
{
    a = getParent(a);
    b = getParent(b);
    if(a>b)
    {
        parent[a] =b;
    }
    else
        parent[b] =a;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 1;
    for(int i=0;i<n;i++)
        parent[i] =i;
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(computers[i][j]==1)
                connect(i,j);
        }
    }
    for(int i=0;i<n;i++)
        parent[i] =getParent(i);

    sort(parent,parent+n);
    int temp =parent[0];
    for(int i=1;i<n;i++)
    {
        if(parent[i] != temp)
        {
            temp =parent[i];
            answer++;
        }
    }
    
    return answer;
}