[ Programmers 43162 ] 네트워크(Python)

문제

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

연결에 대한 이차원 배열이 주어졌을 때, 연결된 네트워크 개수를 return 하는 문제다.

문제 풀이

1. 주어진 이차원 배열로 그래프를 만들었다.
2. 방문하지 않은 정점이면, 방문 체크를 해주고 연결된 정점들을 방문해준다.
3. 이때 방문하지 않은 정점이면 연결되지 않는 네트워크이므로 1을 return, 방문한 정점이면 연결된 네트워크이므로 0을 return 해준다.
4. dfs 함수의 return 값을 answer 변수에 더해준다.

코드

import sys

def solution(n, computers):
    graph = {}
    visited= [0]* n
    answer = 0

    for row_index,rows in enumerate(computers):
        for num_index,num in enumerate(rows):
            if num==1 :
                if row_index not in graph:
                    graph[row_index]=[num_index]
                else:
                    graph[row_index].append(num_index)

    #print(graph)

    def dfs(index):
        #방문한 곳이 아니므로 연결되어 있지 않다 = 다른 네트워크이므로 return 1
        if visited[index]==0:
            visited[index] = 1
            while (graph[index]):
                dfs(graph[index].pop(0))
            return 1
        #방문한 곳이므로 연결되어 있다 = 같은 네트워크이므로 return 0
        else: 
            return 0
            


    for i in range(n):
        answer += dfs(i)
        
    return answer

수정한 코드

한달전에 푼 문제인데, 이제 보니 그래프를 따로 만들지 않아도 된다.
그냥 computers를 이용하면 된다.

import sys

def solution(n, computers):
    graph = {}
    visited= [0]* n
    answer = 0

    def dfs(index):
        if visited[index]==0:
            visited[index] = 1
            for j in range(len(computers)):
                if computers[index][j]==1:
                    dfs(j)
                    computers[index][j] = 0
            
    for i in range(n):
        if visited[i]==0:
            dfs(i)
            answer += 1
        
    return answer