[프로그래머스 level3 네트워크] bfs 활용하기 !

해결해야하는 문제는 다음과 같다.

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

코딩테스트 연습 - 네트워크

 

 

이 문제에서는 모든 네트워크를 탐방하며 연결되지 않은 네트워크가 있다면 네트워크 수를 추가해주어야 한다.

따라서 연결된 네트워크를 모두 탐방하기 위해 bfs 방법을 사용해야겠다고 생각하였다.

 

우선, computers의 배열을 graph로 바꾸었다. 즉, 0번째 컴퓨터에 1번쨰,2번째 컴퓨터가 연결되어 있다면 graph[0] = [1,2] 와같은 방식으로 저장될 수 있도록 형태를 바꾸었다.

그리고 queue에 0을 집어넣고, 0번째 컴퓨터부터 하나씩 순회하도록 하였다.

하나씩 순회할 때, 방문한 노드는 visited 배열을 통해 1로 표시해두었고,

해당 노드에 달려있는 다른 노드들은 graph를 통해 확인하며, 방문하지 않은 경우 queue에 삽입해주었다.

 

현재 queue가 비었는데 아직 탐방하지 못한 노드가 있는 경우 (visited[i]==0인게 존재하는 경우), queue에 현재 0인 노드를 추가해주고 네트워크 한개를 증설해주고 다시 bfs 탐방을 시작하도록 하였다.

 

이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다.

def solution(n, computers):
    answer = 1
    graph = [[] for i in range(n)]
    visited = [0]*n
    for i in range(n):
        for j in range(n):
            if computers[i][j] and i!=j:
                graph[i].append(j)

    queue = [0]
    while queue :
        pos = queue.pop(0)
        visited[pos]=1
        for new_pos in graph[pos]:
            if not visited[new_pos]:
                queue.append(new_pos)
        if len(queue)==0 and sum(visited)<n:
            queue.append(visited.index(0))
            answer += 1
        
    return answer