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

 


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