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

문제

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

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

프로그래머스

• 알고리즘 분류 - 깊이/너비 우선 탐색 (DFS, BFS)
• 난이도 - Level 3

---

접근 방법

컴퓨터 하나씩 DFS로 접근해 같은 네트워크로 연결된 컴퓨터들을 탐색해 방문처리 했다.

새로운 컴퓨터를 파고들 때, 이미 방문된 적이 있다면 다른 네트워크에 포함된 것이므로 카운팅하지 않고, 새로 방문하게 되는 것이라면 새로운 네트워크를 의미하는 것이므로 카운팅해준다.

이때, 연결된 네트워크만 탐색하기 위해서는 주어진 인접행렬 형태보다는 인접리스트 형태가 더 편할 것 같아 인접행렬을 인접리스트로 변환하는 함수를 추가했다.

---

답안 코드

+5

answer = 0

# 인접행렬 -> 인접리스트
def matrix2list(matrix):
    graph = {}
    
    for i in range(len(matrix)):
        for j in range(len(matrix)):
            if i != j and matrix[i][j] == 1:
                if i in graph:
                    graph[i].append(j)
                else:
                    graph[i] = [j]
    
    return graph

def dfs(graph, node, visited):
    global answer
    
    if visited[node]:
        return
    
    visited[node] = True
    
    if node in graph: # 이거 없으면 key error 뜨길래 추가했다..
        for nei in graph[node]:
            dfs(graph, nei, visited)

def solution(n, computers):
    global answer
    visited = [False for _ in range(n)]
    
    g = matrix2list(computers)

    for i in range(n): # 컴퓨터 하나씩 잡고 파고들기
        if not visited[i]: # 이전까지 어떤 네크워크에도 속하지 않았다면 카운팅, 파고들기
            answer += 1
            dfs(g, i, visited)
    
    return answer

 

 

푸는데 두 시간 걸렸다... DFS 아직도 어렵다 ㅠㅠ BFS도 연습해야하는데..