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

문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/43162

 

 

📋 문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.

예를 들어, 컴퓨터 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입니다.

 

 

 

📝 풀이

def dfs(n, i, arr, visited):
  visited[i] = True
  
  for j in range(n):
    if i != j and arr[i][j] == 1 and not visited[j]:
      dfs(n, j, arr, visited)

def solution(n, computers):
  answer = 0
  visited = [False]*n
  
  for i in range(n):
    if visited[i] == False:
      dfs(n, i, computers, visited)
      answer += 1
    
  return answer

 

컴퓨터가 간접적으로 연결되어 있는 경우에도 하나의 네트워크로 취급하기 때문에 컴퓨터의 연결 관계를 알기 위해 방문처리를 할 visited를 만들었다.

이때 visited의 길이는 컴퓨터의 길이와 같고 초기에는 모든 값이 False이다.

 

첫 번째 컴퓨터부터 연결관계를 파악한다.

이때 dfs의 인자로 컴퓨터 개수, 현재 컴퓨터, 컴퓨터의 연결관계, 방문현황이 주어진다.

 

dfs에서는 먼저 현재 살펴보고 있는 컴퓨터를 방문처리한다.

이후 현재 컴퓨터 i와 연결되어 있고 방문하지 않은 컴퓨터가 있는지 살핀다.

i != j를 살피는 이유는 computers[i][i]의 값도 1로 주어지기 때문이다.

 

i와 연결되어 있고 방문하지 않은 컴퓨터가 있으면 그 컴퓨터를 또 파고든다.

더이상 해당하는 컴퓨터가 없다면 이들이 하나의 네트워크가 된 것이므로 answer += 1을 한다.

 

마지막으로 answer에는 네트워크의 수가 담기게 되므로 이를 리턴한다.