[프로그래머스] 네트워크 문제풀이

1. 문제

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

2. 풀이 방법

bfs를 이용하여 문제를 해결합니다. 방문한 노드는 is_visited 배열을 사용하여 표시합니다.

모든 노드를 각각 순차적으로 확인합니다. 방문한 곳이 아니라면 queue에 넣습니다.
queue에 있는 요소를 pop 하면서 연결된 노드가 있는지 확인합니다. 연결된 노드는 방문한 노드가 아니라면 queue에 새로 넣습니다. 모든 연결된 노드를 확인하면 queue에 남아 있는 요소가 없어집니다.
위의 한 과정이 진행되면 한 그룹을 확인한 것입니다. 정답에 1을 더해줍니다.

3. 소스코드

3.1. python 정답 코드

import queue

def solution(n, computers):
    answer = 0
    is_visited = [0] * n
    q = queue.Queue()
    
    for k in range(n):
        if is_visited[k] == 1:
            continue
        answer += 1
        q.put(k)
        while q.qsize() > 0:
            this = q.get()
            is_visited[this] = 1
            for i in range(n):
                if is_visited[i] != 1 and computers[this][i] == 1:
                    q.put(i)
    
    return answer

PREVIOUS[프로그래머스] 타일 장식물 풀이

NEXT[프로그래머스] 베스트앨범