[프로그래머스 Lv.3] 네트워크

def solution(n, computers):
    answer = 0
    graph = [[] for i in range(n)]
    visited = [False]*n
    
    for i,row in enumerate(computers):
        for j,value in enumerate(row):
            if i != j and value == 1:
                graph[j].append(i)
    
    def dfs(n):
        
        if visited[n]:
            return False
        
        visited[n] = True
        
        for i in graph[n]:
            if not visited[i]:
                dfs(i)
        
        return True
        
    for i in range(n):
        if dfs(i):
            answer += 1
    
    return answer

이번 문제는 컴퓨터의 개수 n과 연결에 대한 정보가 담긴 2차원 배열 computers가 주어졌을 때, 직/간접적으로 연결되어있는 네트워크의 개수를 구하는 문제이다.

 

이 문제는 백준에서 출제된 네트워크 문제와 상당히 유사한데 주어진 연결 정보들을 인접 리스트 형태로 저장하고, 각 컴퓨터마다 방문 여부를 기록하는 visited 배열을 가지고 DFS로 풀이하여 매우 쉽게 풀이할 수 있었다.

 

DFS를 복습할 수 있는 간단한 문제였다 :)