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

안녕하세요! 오늘은  프로그래머스의  네트워크 문제를 풀었습니다.

전형적인  union find문제기도 했지만,  한편으론 단순히 dfs돌리면서  같은그룹인지 확인할 수 있는  문제였습니다.

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

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

 

접근과정으로 

1. computers 배열에  들어온 데이터를 갖고  하나씩 순회하면서,  연결관계를 파악했습니다.

2. 두 지점이 연결되있으면 union find를 실행해  하나의 네트워크로 묶었고

3. 최종적으로  네트워크 갯수가 몇개인지를  세었습니다.

 

 

#include <string>
#include <vector>

using namespace std;

//최대 200개의 그룹존재할수있음
int group[201];

int findParent(int a){
    if(group[a] == a){
        return a;
    }
    return findParent(group[a]);
}
void merge(int a, int b){
    int parent_a = findParent(a);
    int parent_b = findParent(b);
    
    //두 그룹이 다르면
    if(parent_a != parent_b){
        //b그룹을 a그룹에 속하게 만들기
        group[parent_b] = parent_a;
    }
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    //각각 자신만 그룹 처리 (초기화)
    for(int i=1;i<=n;i++){
        group[i] = i; 
    }
    
    for(int i=0;i<computers.size();i++){
        for(int j=0;j<i;j++){
            //i랑 j가 연결되있다면
            if(computers[i][j] == 1){
                //unionFind (각 컴퓨터 0부터인데 1부터로 기준바꾸고싶어 +1해서 넘김)
                merge(i+1,j+1);
            }
        }
    }
    
    //그룹확인하며 최종 갯수 세기
    int checked[201]={};
    //물론 set같은 집합에 담아서 갯수세는게 편하지만
    //안쓰고 배열이용해서 갯수세는 식으로 구현해봄.
    for(int i=1;i<=n;i++){
        int p = findParent(group[i]);
        if(checked[p]==0){
            answer++;
            checked[p]=1;
        }
    }
    return answer;
}

 

 

<박기완의 c언어 코딩교육 시리즈 >

게임개발을 희망하는 초등학생, 중학생, 고등학생들을 위한 c언어 책

 

초등, 중등, 고등  1:1 원격 c언어 교육문의

010 - 4537 - 7998

 

현재 대치동 학원에서 코딩강사로 활동중에 있습니다

영재고, 과학고 내신 /

초등, 중등, 고등 입문반, 초급, 중급, 정올반 /

앱, 게임 제작반  문의주세요!