[Programmers] 네트워크(BFS/DFS 풀이 | Python)

🌱 문제

프로그래머스

 

🌱 풀이

전형적인 DFS 알고리즘을 이용해서 푸는 문제입니다.

0. 변수 초기화와 그래프 정보

  

    
    
    
    
  
visited = [False for _ in range(n + 1)]
graph = [[] for _ in range(n + 1)]
answer = 0

for i in range(len(computers)):
    for idx, val in enumerate(computers[i]):
        if i != idx and val == 1:
            graph[i + 1].append(idx + 1)

• 인접 행렬 방식으로 주어진 그래프 정보를 인접 리스트 방식으로 변경합니다. (computers를 for문으로 돌면서 graph에 연결된 노드 정보를 append합니다.)
• visited는 방문한 노드를 방문처리해줄 리스트입니다.

1. dfs 알고리즘

  

    
    
    
    
  
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if visited[i] == False:
            dfs(graph, i, visited)

• dfs가 호출되었을 때의 현재 노드를 방문처리해줍니다.
• 현재 노드와 연결되 노드들에 대해 재귀적으로 dfs를 호출합니다.

2. dfs 탐색하며 네트워크 개수 세기

  

    
    
    
    
  
 for i in range(1, len(computers) + 1):
    if visited[i] == False:
        dfs(graph, i, visited)
        answer += 1

• 방문하지 않은 모든 노드들을 방문하여 dfs탐색합니다.
• 끝까지 탐색하고 나왔을때, answer를 1 증가시킵니다.

 

🌱 코드

  

    
    
    
    
  
def solution(n, computers):
    visited = [False for _ in range(n + 1)]
    graph = [[] for _ in range(n + 1)]
    answer = 0

    for i in range(len(computers)):
        for idx, val in enumerate(computers[i]):
            if i != idx and val == 1:
                graph[i + 1].append(idx + 1)

    def dfs(graph, v, visited):
        visited[v] = True
        for i in graph[v]:
            if visited[i] == False:
                dfs(graph, i, visited)

    for i in range(1, len(computers) + 1):
        if visited[i] == False:
            dfs(graph, i, visited)
            answer += 1

    return answer