[python] 프로그래머스 - 네트워크

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

입출력 예

3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

접근법

이제 알고리즘 문제를 풀고 공부하고 리뷰글을 쓰는 것에 점점 익숙해져 가는 것 같다..! 

아무튼, 이번 문제는 dfs를 사용하면 풀만했던 문제였던 것 같다. dfs/bfs 코드를 외워두니 슥슥 풀 수 있어서 기분이 좋았던 문제!

하지만 삽질이 없었던 건 아니다.. 일단 로직은 이렇다

1. start 숫자가 visited에 있는지 확인한다.
2. dfs 돌려서 그래프를 탐색한다. 이때 방문했던 노드들의 배열을 반환한다.
3. start를 1 증가시킨다 => 이 부분을 생각 못해서 처음에 삽질했다.

이제 코드를 보자.

내 코드

처음 잘못 푼 버전

from collections import defaultdict

def make_dictionary(n, array):
    graph =  defaultdict(list)
    for i in range(n):
        for j in range(n):
            if array[i][j] == 1:
                graph[i] += [j]
        graph[i] = set(graph[i])
    return graph


def solution(n, computers):
    net = 1
    visited = []
    stack = [0]
    graph = make_dictionary(n, computers)
    for i in range(n):
        if stack == []:
            net += 1
            stack.append(i)
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node] - set(visited))
    return net

이러면 테스트 케이스가 딱 절반만 맞았다. 도대체 뭐가 문제야..라고 생각하던 찰나 문제를 알아버렸다.

위와 같은 코드로는 숫자가 순차적으로 연결/끊김을 이루는 경우는 정답이 나오지만 숫자가 뒤죽박죽 연결되어있는 경우 중간 숫자들을 알아낼 방법이 없다.

노드가 3개이고 연결관계는 0:[0,2] 1:[1] 2:[0,2] 라고 생각해보자.. 0번 노드와 2번 노드가 연결되어있다는 것은 알 수 있지만 인덱스 i가 1을 지나쳐버리는 바람에 1번 노드에 대한 dfs는 돌지 못하는 것이다.

지금의 for문을 고수하다가는 코드가 더러워질 것이라 생각했다. 그래서 dfs를 분리하고 solution에는 네트워크의 개수를 세는 것에 집중하는 코드만 남겨놓기로 했다.

함수는 총 세 개가 된다.

1. 주어진 행렬을 python에서 dfs를 돌리기 쉽게 딕셔너리로 바꾸어주는 함수
2. dfs 함수
3. 네트워크를 계산하는 솔루션 함수

변경 코드

from collections import defaultdict

def make_dictionary(n, array):
    graph =  defaultdict(list)
    for i in range(n):
        for j in range(n):
            if array[i][j] == 1:
                graph[i] += [j]
        graph[i] = set(graph[i])
    return graph

def dfs(graph, start):
    visited = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node] - set(visited))
    return visited

def solution(n, computers):
    net = 0
    start = 0
    visited = []
    graph = make_dictionary(n, computers)
    while len(visited) != n:
        if start not in visited:
            visited += dfs(graph, start)
            net += 1
        start += 1
    return net

while 문으로 바꾸고 n대의 컴퓨터가 방문된 상태인지 하나하나 체크해주는 if문을 넣어주면 남은 절반도 아주 잘 돌아간다! 함수를 나누어주니 보기도 깔끔하고 좋은 것 같다.  

while 문이 끝나는 조건은 모든 컴퓨터를 방문했을 때, 즉 visited의 길이가 n과 같아지는 순간이다! 

처음 알고리즘 문제를 풀 때는 너무 못 풀어서 답답한 마음이 늘 앞섰는데, 한두 문제 풀다 보니 문제를 읽고 조금이라도 코드를 뚱땅거릴 수 있음에 재미를 느끼고 있다. 앞으로 더 힘내서 멋진 개발자가 돼야지.