Lv.3 네트워크

[문제]

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

 

프로그래머스의 '네트워크' 문제는 그래프 탐색의 가장 전형적인 유형으로, **"연결된 덩어리(Connected Component)가 총 몇 개인가?"**를 찾는 문제입니다.

'타겟 넘버'가 트리 구조를 따라 내려가는 방식이었다면, 이 문제는 그물망처럼 연결된 정점들을 방문하며 구역을 나누는 방식입니다.

---

1. 상태 시각화하기

컴퓨터들이 노드(점)이고, computers 배열이 간선(선) 정보입니다.

• computers[i][j] == 1이면 $i$번 컴퓨터와 $j$번 컴퓨터가 연결되어 있다는 뜻입니다.
• 우리는 모든 컴퓨터를 하나씩 확인하면서, **"아직 방문하지 않은 컴퓨터를 발견하면 그 컴퓨터와 연결된 모든 컴퓨터를 싹 다 방문(체크)한다"**는 전략을 세워야 합니다.

2. 접근 아이디어: "팀 나누기"

1. 방문 기록부 만들기: 각 컴퓨터를 방문했는지 체크할 visited 리스트를 만듭니다. (예: [False, False, False])
2. 전수 조사: 0번 컴퓨터부터 마지막 컴퓨터까지 루프를 돕니다.
3. 새로운 네트워크 발견:
   • 만약 $i$번째 컴퓨터를 아직 방문하지 않았다면? -> 새로운 네트워크(덩어리)를 하나 찾은 것입니다! answer를 1 올립니다.
   • 이제 이 $i$번 컴퓨터와 연결된 모든 친구들을 찾아가서 "방문함" 도장을 찍어줘야 합니다. (이때 DFS나 BFS를 사용합니다.)
4. 확산 (DFS/BFS):
   • $i$번과 연결된 $j$번을 찾고, 다시 $j$번과 연결된 $k$번을 찾는 식으로 계속 파고들어 visited를 True로 바꿉니다.
5. 모든 컴퓨터를 돌 때까지 반복합니다.

3. DFS vs BFS 어떤 게 좋을까?

이 문제에서는 어느 것을 써도 상관없지만, **DFS(재귀)**가 구현이 조금 더 간결합니다.

• DFS: "나랑 연결된 애 있어? 그럼 걔한테 가서 또 연결된 애 있는지 물어봐!" (깊게 파고들기)
• BFS: "나랑 연결된 애들 일단 다 줄 세워봐. 하나씩 방문 처리하자." (넓게 퍼지기)

---

💡 핵심 포인트

• computers[i][i]는 항상 1입니다. (자기 자신과의 연결) 탐색할 때 이 부분을 주의하세요.
• 이 문제는 "경로"를 찾는 게 아니라 **"방문 여부"**만 중요합니다. 한 번 True가 된 컴퓨터는 다시 검사할 필요가 없습니다.

이번에도 가장 직관적인 DFS(깊이 우선 탐색) 방식으로 풀어보겠습니다. '네트워크'의 핵심은 **"한 놈만 걸려라, 연결된 애들은 다 방문 처리한다"**는 마인드입니다.

---

Python 코드 정답

Python

 

def solution(n, computers):
    answer = 0
    visited = [False] * n  # 방문 여부를 체크할 리스트

    def dfs(node):
        visited[node] = True  # 현재 컴퓨터 방문 처리
        
        # 현재 컴퓨터(node)와 연결된 다른 컴퓨터(i)를 찾음
        for i in range(n):
            # 연결되어 있고(1), 아직 방문하지 않았다면
            if computers[node][i] == 1 and not visited[i]:
                dfs(i)  # 그 친구로 이동해서 다시 탐색 (재귀)

    # 모든 컴퓨터를 하나씩 확인
    for i in range(n):
        if not visited[i]:  # 아직 방문 안 한 컴퓨터라면 = 새로운 네트워크의 시작!
            dfs(i)          # 이 컴퓨터와 연결된 모든 컴퓨터를 방문 처리
            answer += 1     # 네트워크 개수 +1
            
    return answer

---

코드 풀이 가이드

1. visited 리스트: 컴퓨터가 3대라면 [False, False, False]로 시작합니다. 방문한 곳은 True로 바꿔서 중복 계산을 막습니다.
2. 메인 루프 (for i in range(n)):
   • 0번부터 끝까지 훑습니다.
   • 만약 0번이 방문 안 된 상태라면, answer를 올리고 0번과 연결된 모든 컴퓨터를 찾아 떠납니다.
3. dfs(node) 함수:
   • 이 함수는 특정 컴퓨터와 연결된 **"모든 줄기"**를 다 훑고 나옵니다.
   • computers[node][i] == 1 조건은 node번 컴퓨터와 i번 컴퓨터가 이어져 있다는 뜻입니다.
   • 재귀가 한 번 끝나고 메인 루프로 돌아오면, 하나의 네트워크 덩어리가 완전히 처리된 상태가 됩니다.

BFS(너비 우선 탐색)로 풀고 싶다면?

큐(collections.deque)를 사용하여 구현할 수도 있습니다. 로직은 같습니다.

Python

 

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    for i in range(n):
        if not visited[i]:
            # BFS 시작
            queue = deque([i])
            visited[i] = True
            while queue:
                curr = queue.popleft()
                for next_node in range(n):
                    if computers[curr][next_node] == 1 and not visited[next_node]:
                        visited[next_node] = True
                        queue.append(next_node)
            answer += 1
    return answer

요약하자면

• 타겟 넘버: "숫자를 쓸까 말까?"의 조합을 찾는 문제 ($2^N$ 경로)
• 네트워크: "누구랑 연결되어 있지?"의 덩어리를 찾는 문제 (그래프 탐색)

[나의 풀이]

 

[다른 사람 풀이]

 

[배운 스킬]