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

문제

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

코딩테스트 연습 - 네트워크

---

문제 요구 조건

• 그래프의 연결성분 찾기

 

문제 요건 분석

• 그래프의 경우 무향 그래프임.
• 입력으로 주어지는 그래프가 인접행렬로 구현되어 있기 때문에, 인접리스트로 구현할 시 (defaultdict에 넣어주는 형태로) 무향 그래프임에도 불구하고 노드를 뒤바꿔 추가해주는 작업을 하지 않아도 됨.
• 그래프 탐색이기 때문에 dfs를 통해 구현함.
• 연결성분의 개수를 구하는 것이기 때문에 하나의 노드에 연결된 지점을 모두 다 탐색하면 1을 리턴하는 방식으로 구현.

 

코드

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def solution(n, computers):
    answer = 0
    visited = []
    graph = defaultdict(list) # undirected graph
    
    def dfs(v):
        visited.append(v)
        for v_next in graph[v]:
            if v_next not in visited:
                dfs(v_next)
        
        return 1 # 해당 노드와 연결된 노드가 없을 때
    
    # 인접리스트로 그래프 구현
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if computers[i][j] == 1:
                graph[i].append(j)

    
    for i in range(n): # node 탐색
        if i not in visited:
            answer += dfs(i) 
    
    return answer

 

어려웠던 점

• 재귀로 dfs를 구현했는데 종료조건을 어떻게 해주어야할지 파악을 빨리 못함. 실제로 dfs를 재귀적으로 호출할 때에 return을 해주면서 백트래킹이 안되는 문제가 발생함.
• 재귀로 dfs를 구현하는 게 아직 익숙지 않아서 이전에 구현해두었던 걸 참고로 함.

 

개선할 부분

• dfs를 재귀로 구현하는 연습을 더욱더 많이 해볼 것.
• bfs로 풀면 어떻게 될지?