그래프를 여러 집단으로 나누는 방법

1. 문제

 

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

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

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.

 

예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고,

 

컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.

 

따라서 컴퓨터 A,B,C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

 

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때,

 

네트워크 개수를 return하도록 solution 함수를 작성하세요.

 

 

2. 제한사항

 

컴퓨터의 개수 n은 1이상 200이하인 자연수

 

각 컴퓨터는 0부터 n-1인 정수로 표현

 

i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현

 

computers[i][i]는 항상 1

 

 

3. 입출력 예시

 

 

4. 입출력 설명

 

예시1

 

예시2

 

5. 나의 풀이

 

전체 node의 집합을 만들고 연결된 network의 집합을 구하면

 

전체 node의 집합에서 연결된 network의 집합을 빼면 다음 후보군 node의 집합이 생길 것이다

 

이게 핵심 아이디어라고 생각하고 시작

 

def solution(n,computers):
    
    answer = 0
    
    computer = set(range(n))
    
    all_network = []

 

전체 node의 집합을 computer로 초기화하고 

 

첫 검사할 노드는 computer의 최솟값이므로 min(computer)로 찾을 수 있고

 

그러면 이 노드에 연결된 리스트는 computers[min(computer)]로 쉽게 찾을 수 있다

 

def solution(n,computers):
    
    answer = 0
    
    computer = set(range(n))
    
    all_network = []
    
    while computer != set():
        
        network = set()
        
        loc = min(computer)
        
        for ind,edge in enumerate(computers[loc]):
            
            if edge == 1:
            
                network.add(ind)
                
        all_network.append(network)
        
        computer -= network
    
    answer = len(all_network)
    
    return answer

 

전체 노드의 집합인 computer가 공집합이 될때까지 while문을 반복하고

 

연결된 노드들의 집합인 network = set()으로 초기화하고 첫 검사할 노드 loc = min(computer)로 찾고

 

이 노드와 연결된 edge의 리스트들이 computers[loc]로 찾을 수 있어서 for문으로 순회한다

 

edge가 1이면 해당 노드와 연결되어있다는 뜻으로 index를 network에 넣으면 되는데

 

enumerate를 이용하면 index를 쉽게 찾을 수 있다

 

내부 for문을 전부 돌면 하나의 연결된 network들이 구성되고 이를 all_network에 넣어준다

 

그리고 전체 노드의 집합에서 연결된 network의 집합을 뺀 집합이 다음에 검사해야할 노드들의 집합이 된다

 

공집합이 될 때까지 반복하면 되는데....

 

 

문제는 0,1,2를 하나의 network로 만들어야하는데 0,1과 1,2로 잘라서 들어가진다는게 문제

 

그렇다면 어떻게 해야하는가??

 

알고리즘을 다시 천천히 생각을 해보면....

 

---------------------------------------------------------------------------------------

 

예제 2로 예를 들어서 생각을 해보면

 

처음에 0을 검사하는데... 0에 연결된 노드들을 전부 network에 집어 넣는다

 

그러면 {0,1}이 들어가있는데... 여기서 끝내는게 아니라

 

그 다음 1에 연결된 노드들을 추가적으로 검사해야한다

 

그러면 1에 연결된 노드는 {0,2}이므로 {0,1}에 {0,2}가 들어가서 {0,1,2}가 만들어진다

 

----------------------------------------------------------------------------------------

 

그래서 검사하고자하는 노드 리스트 comp_list = []를 추가적으로 초기화시키고 시작을 해보자

 

def solution(n,computers):
    
    from collections import deque
    
    answer = 0
    
    computer = set(range(n))
    
    all_network = []
    
    exam = deque()
    
    comp_list = []

comp_list는 검사가 완료된 노드들을 집어넣을거고

 

exam=deque()는 하나의 network를 구성할때 검사해야할 노드들을 모아놓을거

 

def solution(n,computers):
    
    from collections import deque
    
    answer = 0
    
    computer = set(range(n))
    
    all_network = []
    
    exam = deque()
    
    comp_list = []
        
    while computer != set():
        
        loc = min(computer)
        
        network = set()
        
        for ind,edge in enumerate(computers[loc]):
            
            if edge == 1:
                
                network.add(ind)
                
                exam.append(ind)
        
        comp_list.append(loc)

 

그러면 위에서 썼던 알고리즘 그대로 처음 검사할 위치 loc=min(computer)로 찾고

 

연결된 노드들의 집합 network = set()으로 초기화한 다음에

 

loc와 연결된 edge들의 리스트 computers[loc]를 순회한다

 

이제 edge==1이면 해당 노드와 연결되어 있다는 뜻이므로 index를 network와 exam에도 추가적으로 집어넣는다

 

exam은 다음에 또 검사해야할 리스트들이 될 것이고

 

한번의 검사가 끝났기때문에 현재 loc를 comp_list에 집어넣는다

 

def solution(n,computers):
    
    from collections import deque
    
    answer = 0
    
    computer = set(range(n))
    
    all_network = []
    
    exam = deque()
    
    comp_list = []
        
    while computer != set():
        
        loc = min(computer)
        
        network = set()
        
        for ind,edge in enumerate(computers[loc]):
            
            if edge == 1:
                
                network.add(ind)
                
                exam.append(ind)
        
        comp_list.append(loc)
        
        while exam != deque():
            
            loc = exam.popleft()
            
            if loc in comp_list:
                
                continue
            
            else:
                
                for ind,edge in enumerate(computers[loc]):
                    
                    if edge == 1:
                        
                        exam.append(ind)
                        
                        network.add(ind)
                
                comp_list.append(loc)

 

다음에 exam에 들어간 노드들에 대해 추가적으로 검사하는 반복문을 수행한다

 

exam에서 popleft로 빼면 다음에 검사할 노드 loc가 나오는데

 

만약 comp_list에 이 loc가 존재한다면 이미 검사가 끝났으므로 continue로 반복문을 한번 스킵하고

 

들어가 있지 않다면 바로 위에서 사용한 알고리즘으로 network와 exam을 계속해서 구성한다

 

network는 집합이라 중복이 알아서 제거되고 exam에 중복이 들어가더라도 comp_list에 있으면

 

skip하라고 되어있으니 괜찮아

 

이 알고리즘을 추가하면 분명 {0,1}, {1,2}가 아니라 {0,1,2}로 연결될 것이다

 

def solution(n,computers):
    
    from collections import deque
    
    answer = 0
    
    computer = set(range(n))
    
    all_network = []
    
    exam = deque()
    
    comp_list = []
        
    while computer != set():
        
        loc = min(computer)
        
        network = set()
        
        for ind,edge in enumerate(computers[loc]):
            
            if edge == 1:
                
                network.add(ind)
                
                exam.append(ind)
        
        comp_list.append(loc)
        
        while exam != deque():
            
            loc = exam.popleft()
            
            if loc in comp_list:
                
                continue
            
            else:
                
                for ind,edge in enumerate(computers[loc]):
                    
                    if edge == 1:
                        
                        exam.append(ind)
                        
                        network.add(ind)
                
                comp_list.append(loc)
                
        all_network.append(network)
        
        computer -= network
        
    answer = len(all_network)
    
    return answer

 

6. 되돌아보기

 

핵심아이디어를 잘 생각했고

 

처음 생각할 때는 막혔지만 왜 막혔는지 잘 이해했고 문제점을 잘 고쳤다

 

중복을 제거하기 위해 set을 활용하고

 

그래프를 탐색해갈때 탐색완료된 집합 comp_list를 생각해야하는지 말아야하는지 기억

 

이 경우는 계속해서 탐색해나가야하기 때문에 comp_list를 생각해야한다

 

단순하게 연결된것만 찾아버리면 {0,1,2}로 연결시켜야할 것을 {0,1}, {1,2}로 나눠버리기 때문에