프로그래머스 등급3 - 네트워크

네트워크 문제 바로 가기

풀이 날짜: 2026-05-01

baekjoon 알고리즘 문제 풀이

풀이 코드


n = int(input())
computers = [list(map(int, input().split())) for _ in range(n)]

visited = [False] * n

def dfs(start):
    visited[start] = True

    for i in range(n):
        if computers[start][i] == 1 and not visited[i]:
            dfs(i)
    
count = 0

for i in range(n):
    if not visited[i]:
        dfs(i)
        count += 1

print(count)

문제 핵심

여기서 “네트워크”란 서로 직·간접적으로 연결된 컴퓨터들의 집합을 의미한다. 즉, 한 컴퓨터에서 다른 컴퓨터로 연결을 따라가며 도달할 수 있다면 같은 네트워크로 간주한다.

입력 데이터의 의미 (2차원 배열 해석)

입력으로 주어지는 computers는 2차원 배열이며, 이는 컴퓨터 간 연결 관계를 나타낸다. computers[i][j] == 1이면 i번 컴퓨터와 j번 컴퓨터가 연결되어 있다는 뜻이고, 0이면 연결되어 있지 않다는 의미이다. 이러한 형태는 그래프를 인접 행렬로 표현한 것이며, 이를 통해 어떤 노드가 어떤 노드와 연결되어 있는지 쉽게 확인할 수 있다.

문제 접근 방법

이 문제는 결국 “연결된 컴퓨터들을 하나의 그룹으로 묶는 문제”이다. 이를 그래프 관점에서 보면, 연결된 노드들을 하나의 컴포넌트로 묶는 작업과 동일하다.

DFS

DFS는 특정 컴퓨터에서 시작하여 연결된 모든 컴퓨터를 방문한다. 즉, 한 컴퓨터에서 DFS를 시작하면 그 컴퓨터와 연결된 모든 컴퓨터들이 하나의 네트워크로 묶인다. 이때 방문한 컴퓨터는 다시 탐색하지 않도록 visited 배열을 사용하여 관리한다.

방문 배열의 필요성

visited 배열은 각 컴퓨터가 이미 탐색되었는지를 기록하기 위해 사용된다. 만약 방문 체크를 하지 않으면 같은 컴퓨터를 여러 번 탐색하게 되어 무한 루프가 발생하거나 비효율적인 코드가 된다. 따라서 DFS를 시작할 때 현재 노드를 방문 처리하고, 이후 연결된 노드들 중 아직 방문하지 않은 노드만 재귀적으로 탐색한다.

네트워크 개수 세기 (핵심 로직)

모든 컴퓨터를 순회하면서 아직 방문하지 않은 컴퓨터를 발견하면, 이는 새로운 네트워크의 시작점이 된다. 이때 DFS를 실행하여 해당 컴퓨터와 연결된 모든 컴퓨터를 방문 처리하고, 네트워크 개수를 1 증가시킨다. 결과적으로 DFS를 몇 번 실행했는지가 곧 네트워크의 개수가 된다.

핵심 정리

이 문제는 그래프를 직접적으로 다루는 것처럼 보이지 않지만, 실제로는 컴퓨터 간 연결 관계를 그래프로 변환하여 해결하는 문제이다. 각 DFS 실행이 하나의 네트워크를 의미하며, 방문하지 않은 노드에서 DFS를 시작할 때마다 네트워크 개수를 증가시키면 된다. 즉, 이 문제의 핵심은 “연결된 노드들을 하나의 그룹으로 묶고, 그 그룹의 개수를 세는 것”이다.

Vienna sausage