문제

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

접근 방식

연결된 컴퓨터 묶음이 몇개인가를 묻는 문제

1. 아직 방문하지 않은 컴퓨터를 찾는다.
2. 방문하지 않은 컴퓨터에 방문하여, 그 컴퓨터와 연결된 애들을 전부 방문한다.
3. 더이상 연결된 곳이 없다면 네트워크 1개를 발견한 것
4. 다시 아직 방문하지 않은 컴퓨터를 찾는다.
   (반복 수행)

DFS 를 한번 돌릴 때마다 네트워크 1개를 찾는 것과 동일

준비물 챙기기

1. 연결 여부가 포함된 맵
   • 행과 열이 의미하는 바가 무엇인지 생각해보기
2. 방문한 컴퓨터인지 표시하는 컴퓨터 방문록
   • N개의 컴퓨터라면 N만큼 길이의 방문 배열 존재

   visited = [False] * n

DFS 함수가 해야하는 일 정리

1. 현재 컴퓨터 방문처리
2. 현재 컴퓨터와 연결된 부분 (맵상에서 1인부분) 확인
3. 연결되어있는데, 아직 방문 안했다면 재귀로 방문
   • computers[now][next] == 1 이면 무슨 뜻일까?
     now번 컴퓨터와 next번 컴퓨터가 연결되어 있다는 의미

해결

def solution(n, computers):
    # computers 행렬에서 행과 열은 각각 컴퓨터의 총 개수와 동일
    # 방문한 컴퓨터를 또 방문하지 않도록 방문 체크 배열 생성
    visited = [False] * n
    # 방문 여부 확인후
    #   방문 x => 그 노드를 시작으로 dfs => 네트워크 + 1
    #   방문 o => pass
    networks = 0
    def dfs(now):
        # 방문 표시
        visited[now] = True
        # 하나의 컴퓨터 종류에 대해서 연결 여부 탐색
        for next in range(n):
            # 연결이 되어있고 (1이고) 방문하지 않은 경우 dfs 진행 (파고 들어가)
            if computers[now][next] == 1 and not visited[next]:
                dfs(next)
    # 다음 컴퓨터로 이동하는 로직 (컴퓨터 마다 하나씩 실행)
    for i in range(n):
        if not visited[i]:
            dfs(i)
            networks += 1
    return networks

탬플릿

1. 네트워크 개수
2. 섬의 개수
3. 연결요소개수
4. 무리 개수

for 모든 정점:
    아직 방문 안 했으면:
        탐색 한번
        count += 1