[프로그래머스] 네트워크 (python) - BFS/DFS

# 문제 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

# 아이디어 

이 문제는 개인적으로 백준 # 2606번 바이러스 문제와 비슷하다는 생각이 가장 먼저 들었다. 그래서 비슷하게 DFS로 접근해야겠다는 생각을 가장 먼저 했던 것 같다. 하지만 문제 파악 후 바이러스 문제와는 살짝 다른 점이 있는데, 이는 다음과 같았다. 

바이러스 문제는 우선 1로부터 edge로 이어진 모든 노드의 개수를 반환하는 문제였다. 하지만 내가 파악한 이번 네트워크 문제는 이어져 있는 "뭉탱이"의 개수를 세는 것이다. 따라서 다른 점이 있어서 바이러스 문제의 코드베이스로는 풀기 어려운 문제였다. 

앞서 말한 것 처럼 나는 이 문제를 뭉탱이 개수를 세는 문제로 파악했다. 따라서 이러한 문제에는 DFS가 탁월할 것이라고 생각했다. 

하지만 주의해야 할 것은 이렇게 하나로 떨어진 외딴 뭉탱이도 하나의 뭉탱이로 세줘야 한다는 것이었다. 

 

# Code 

우선 위와 같은 아이디어를 DFS로 구현한 코드는 다음과 같다. 

# 변형하는 역량이 중요한 문제 

# main function
def solution(n, computers):

  def dfs(v):
    visited[v] = True
    
    for nei in range(n):    # 인접노드 탐구 
      if not visited[nei] and computers[v][nei]:    # unvisited + 인접할 때 
        dfs(nei)
        
  count = 0   
  visited = [False] * (n)   

  for node_idx in range(n):
  
    if not visited[node_idx] :
      dfs(node_idx)
      count += 1         # dfs 끝나면 count 해주기 
  
  return count

여기서 주의해야할 점은 solution 함수 안에 들어있는 dfs 함수를 밖으로 꺼내면 답이 다르게 나온다는 점이다. (왜지?)  이 코드의 중요한 포인트는 unvisited node를 대상으로 dfs를 재귀함수로 한바탕 마치고 count를 최종적으로 해준다는 점이다. 이 과정을 놓쳐서 구현할 때 어려움을 겪었다. 

위 프로세스를 동일하게 BFS로도 구현할 수 있다. 이는 구글링을 참고하였다.