[프로그래머스] '네트워크' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]

---

 

문제 설명

 

 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

 

 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

 

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

 

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1
5	[[1,0,1,0,0],[0,1,0,1,0],[1,0,1,1,0],[0,1,1,1,0],[0,0,0,0,1]]	2

알고리즘 분석

 

• 나의 풀이

def something(n, answer):
    for i in range(n):
    	# 비교할 set자료형, 빈 set자료형, set_i가 존재하는 요소의 개수
        set_i, tmp, count = set([i]), set(), 0 
        for j in answer[:]:
            if set_i & j: # 교집합이 존재할 경우(j 안에 set_i가 존재할 경우)
                count += 1
                tmp = tmp | j # tmp에 j의 요소를 추가 
        if count > 1: # count가 1보다 클 경우 
        	# answer의 요소 중에 set_i와 교집합이 존재하는 모든 값을 set()으로 만듬
            answer = list(map(lambda x: set() if x & set_i else x, answer))
            answer.append(tmp) # answer에 tmp를 추가 
            while set() in answer: answer.remove(set()) # answer 안의 모든 set()를 삭제
    return answer # answer을 반환 

def solution(n, computers):
    answer = []
    for computer in computers: # 컴퓨터의 관계도를 차례로 불러옴
        var = set() # 빈 집합 자료형을 선언 
        # 컴퓨터의 관계도를 참고해서 var에 저장 
        var.update([idx for idx, com in enumerate(computer) if com==1])
        for ans in answer[:]: # answer에 저장된 set 값들을 차례로 불러옴
            if ans & var: # ans와 var의 교집합이 존재할 경우 
                answer.remove(ans) # answer에서 ans의 값을 지닌 요소를 삭제 
                answer.append(ans | var) # answer에 ans와 var의 합집합을 추가 
                break
        else: # for문에서 break가 실행되지 않았을 경우 
            answer.append(var) # var를 answer에 추가 

    answer = something(n, answer) # answer의 요소들이 서로 교집합인 경우 합집합으로 값을 변경 
    return len(answer)

 

원래는 something 함수를 만드는 것은 계획에 없었다. 

solution 함수만으로 처리하려고 했는데 something 함수를 만들면서 상당히 복잡해져 버린 것 같다. 

 

something 함수를 만들수 밖에 없었던 이유는 위의 입출력 예시의 3번 때문이다. 

 

3번 예시에서는 중간에 "[{0, 2}, {1, 3}]"의 값을 가지게 되는데

0번과 2번, 1번과 3번 컴퓨터가 연결되어 2개의 네트워크를 갖게 된다.

하지만 바로 다음에 "[{0, 2, 3}, {1, 2, 3}]"라는 값을 갖게된다. 

이런 결과가 나오는 이유는 기존에 연결되지 않았던 두 네트워크의 각각의 한 요소끼리 연결되면서 한 개로 통합되어야 하는 네트워크가 두 개로 나뉘어 버린 것. 

 

이 문제를 해결하기 위해서 마지막에 서로 겹치는 요소를 모두 하나로 합치는 something 함수를 만들었다.