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

문제 링크

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

프로그래머스

 

문제 접근 방식

노드끼리 집단을 이루고 있으며 우리는 이 집단(네트워크)의 개수를 구해야한다.

각 집단의 한 노드를 시작으로 연결된 모든 노드를 BFS로 방문처리 하고,

네트워크의 개수를 1씩 증가시키면 네트워크의 개수가 구해진다.

 

 

처리과정

<메인 함수>

1. 모든 노드를 순회하여, 아직 방문하지 않는 노드를 하나 선택한다.

    1.1. 이 노드에 대해 BFS 함수를 실행시켜서 연결된 모든 노드를 방문처리한다.

    1.2. 해당 노드의 네트워크를 BFS로 방문처리했다면 개수를 1 증가시킨다.

 

<BFS 함수>

1. 특정 노드를 큐에 넣고 방문처리한다.

2. 큐가 빌 때까지 반복한다.

    2.1. 노드를 꺼내고, 이 노드와 연결되어 있으며 아직 방문하지 않는 노드라면 

          큐에 넣고 방문처리한다.

 

 

코드

def bfs(n,computers,start,visited):
    q=[start]
    visited.add(start)
    
    while q:
        node=q.pop(0)
        for i in range(n):
            if computers[node][i] ==1 and i not in visited:
                q.append(i)
                visited.add(i)
    return
    
def solution(n, computers):
    answer=0
    visited=set()
    for i in range(n):
        if i not in visited:
            bfs(n,computers,i,visited)
            answer+=1
    return answer

 

 

회고

DFS 또는 BFS 를 통해 연결된 노드를 방문처리하는 것이 핵심인 알고리즘.

노드의 번호가 정해져있기 때문에 set함수를 이용해서 방문처리를 진행했다.