문제 설명

문제는 이 곳 링크를 참조하길 바란다.

• https://programmers.co.kr/learn/courses/30/lessons/43162

전체 코드

from collections import deque

def solution(n, computers):
    def bfs(v):
        q = deque()
        q.append(v)
        visited[v] = 1
        answer = [v]

        while q:
            v = q.popleft()

            for i in range(n):
                if computers[v][i] == 1 and visited[i] == 0:
                    answer.append(i)
                    q.append(i)
                    visited[i] = 1

        return answer
    visited = [0]*(n)
    result = []
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if (computers[i][j] == 1) and (visited[i] == 0):
                result.append(bfs(i))
    
    return len(result)

해결 방법

기초적인 그래프 문제이다. 문제의 핵심은 computers에서 이어져 있는 정점들의 갯수를 세는 것이므로 visited라는 중복을 제거해주는 리스트를 선언하고 computers의 원소가 1이고 visited[인덱스]가 0이라면 그 때 정점에서 bfs를 실행하여 연결되어 있는 정점들의 리스트를 answer이라는 리스트에 반환해주고 result라는 리스트에 그 값을 append 시켜준다. 그리고 마지막으로 result의 길이를 구해주면 정답.