[Programmers][Python] 네트워크

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: Lv.3
• 문제 유형: DFS/BFS
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

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

프로그래머스

 

 

문제 풀이

main 함수

• visited 배열로 컴퓨터가 탐색되었는지 여부를 확인한다. (초기값 False)
• network_cnt 로 네트워크 개수를 세어준다. 
• for 루프로 각 컴퓨터를 순차적으로 탐색한다. 
  • 방문하지 않은 컴퓨터를 발견하면, 그 컴퓨터를 시작점으로 dfs를 호출해서 해당 네트워크에 속한 모든 컴퓨터를 탐색한다. 
  • dfs 호출 후에는 network_cnt를 1 증가시켜 새로운 네트워크를 추가해준다. 

dfs 함수

• v번 컴퓨터를 시작으로 dfs를 수행한다. 
• visited 배열로 해당 컴퓨터가 이미 탐색되었는지 표시한다. 
• 연결된 컴퓨터 중 방문하지 않은 컴퓨터가 있으면 (not visited[i]) 재귀적으로 dfs를 호출하여 게속 탐색한다. 
• 이 과정을 통해 하나의 네트워크에 속한 모든 컴퓨터를 탐색하게 된다. 

 

예제 1, 예제 2

[코드]

def dfs(computers, visited, v):
    visited[v] = True

    for i in range(len(computers)):
        if computers[v][i] == 1 and not visited[i]:
            dfs(computers, visited, i)


def solution(n, computers):
    visited = [False] * n
    network_cnt = 0

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

    return network_cnt