(Python) 프로그래머스 - 네트워크

27 Feb 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

from collections import deque


def solution(n, computers):
    answer = 0
    visit = [0] * n
    start = 0
    while 0 in visit:
        if visit[start] == 0:
            bfs(start, computers, n, visit)
            answer += 1
        start += 1

    return answer


def bfs(start, computers, n, visit):
    q = deque([start])
    visit[start] = 1

    while q:
        start = q.pop()
        for j in range(n):
            if visit[j] == 0 and computers[start][j] == 1:
                q.append(j)
                visit[j] = 1

print(solution(4, [[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 1]]))

방문한 곳을 저장하는 리스트를 하나 만들고 노드 하나씩 선정해서 bfs를 돌리면 된다.