문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

입출력 예

n	computers							return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

접근 방법

이번 문제는 연결된 노드들의 그룹 개수를 세는 문제이다. 이러한 문제는 깊이우선탐색이나 너비우선탐색으로 해결이 가능하다. 나는 깊이우선탐색을 활용하여 해결하였다. 우선 그래프를 인접 리스트 형태로 구현한다. 그리고 방문처리를 적용한다. 이 문제에서 탐색이 끝나면 n개의 노드가 모두 방문처리가 되어 있어야 한다. 그리고 dfs함수에는 현재 노드와 연결된 노드 중 방문처리가 되지 않은 노드에 대한 dfs 재귀 호출을 진행하도록 한다. 그리고 n번 반복하는 반복문에서 dfs함수를 호출할 때마다 answer를 1씩 증가시켜 그룹의 개수를 세주는 방식으로 해결하였다.

• 정답을 저장하는 변수 answer를 0으로 선언한다.
• 그래프를 저장할 리스트 graph를 2차원 리스트로 선언한다.
• computers의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> computers[i]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
  --> 만약 i와 j가 같을 경우 다음 반복으로 넘어간다.
  --> 그 외에는 computers[i][j]가 1일 경우 graph[i]에 j를 넣어준다.
  (양방향 연결이지만 각 노드의 연결 정보에서 서로가 서로를 연결하고 있음을 알리기 때문에 양방향처리할 필요가 없다.)
• 방문처리에 사용할 리스트 visited를 False n개로 채운다.
• dfs함수를 cur을 인자로 갖도록 선언한다.
  -> visited[cur]을 True로 갱신하여 방문처리한다.
  -> graph[cur]을 순회하는 nxt에 대한 for문을 돌린다.
  --> 만약 visited[nxt]가 False일 경우, dfs(nxt)를 재귀호출한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> 만약 visited[i]가 False일 경우,
  --> dfs(i)를 호출한다.
  --> answer를 1 증가시킨다.
• answer를 반환한다.

solution.py

def solution(n, computers):
    answer = 0
    graph=[[] for _ in range(n)]
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if i==j:
                continue
            elif computers[i][j]==1:
                graph[i].append(j)
    visited=[False for _ in range(n)]
    def dfs(cur):
        visited[cur]=True
        for nxt in graph[cur]:
            if not visited[nxt]:
                dfs(nxt)
    for i in range(n):
        if not visited[i]:
            dfs(i)
            answer+=1
    return answer