[프로그래머스] lv3 네트워크 / 파이썬, 고득점kit

문제 설명 ==> 프로그래머스: 네트워크

정수 n이 주어지고 그 정수에 알맞은 n X n 행렬이 주어진다. 

주의점!

• 주대각성분은 모두 1이다. 문제에서는 (computer[i][i]는 항상 1입니다)라고 적어놓았다.
• 그래프의 특징을 보면 대칭행렬이다.

 

방문 위치를 나타내는 visited를 이용해서 풀었다. 약간 백준 스타일..

주어진 computers 이외에 graph라는 이름의 n차원 그래프를 생성해 문제를 푼다.

주대각성분은 자기자신과의 연결을 의미하니까 노드의 연결에서 제외한다.

from collections import deque

def func(n, computers, graph):
    for i in range(n):
        for j in range(n):
            if i != j and computers[i][j] == 1:
                graph[i].append(j)
                
def bfs(v, visited, computers, graph):
    q = deque()
    q.append(v)
    visited[v] = 1
    while q:
        now = q.popleft()
        for i in graph[now]:
            if visited[i] == 0:
                visited[i] = 1
                q.append(i)

def solution(n, computers):
    answer = 0
    visited = [0] * (n)
    graph = [ [] for _ in range(n) ]
    func(n, computers, graph)
    for i in range(n):
        if visited[i] == 0:
            bfs(i, visited, computers, graph)
            answer += 1
    return answer

 

한 번 bfs()를 호출할 때 마다 네트워크의 개수를 찾는 방식이라 생각하면 된다.

비슷한 문제 ==> 백준 11724번: 연결 요소의 개수