Network의 개수 구하기

문제 : 프로그래머스 – 네트워크 (링크가 짤렸다면 이곳에서 확인해 주세요)

아이디어

  1. 노드의 연결성이 끊어질때 network_count를 1씩 증가시킨다. 노드의 연결성이 끊어졌는지 아는 방법은, 주어진 인접행렬(computers)를 너비우선탐색하면서 Queue에 아무것도 없는지를 확인하는것이다.
  2. 들린 노드는 또 들리지 않아야 하는데, 이는 인접행렬에 들린 노드를 0으로 바꿔주면 된다. 다음에 너비탐색을 할때, 해당 노드가 0이면 Queue에 넣지 않는다.
  3. Queue가 비어서 이제 다음 네트워크를 찾으려고 다른 시작점 노드를 찾기 위해서는 인접행렬의 행의 모든 원소의 합이 0보다 큰지를 확인해야한다. Queue는 비었는데 합이 0보다 크다면 그 노드는 끊어져있었고 새로운 네트워크안에 포함된 노드라는 의미이다.

코드

from collections import deque
q = deque()

def bfs(index, computers):
  q.append(index)
  while not (len(q) == 0):
    i = q.popleft()
    computers[i][i] = 0

    for z in range(len(computers[i])):
      if computers[i][z] == 1:
        q.append(z)
        computers[i][z] = 0
        computers[z][i] = 0

def solution(n, computers):
  network_count = 0
  for i in range(len(computers)):
    if sum(computers[i]) > 0 :
      bfs(i, computers)
      network_count = network_count+1
  
  return network_count

computers = [
  [1,1,0],
  [1,1,1],
  [0,1,1]
]

print(solution(3, computers)) # 1

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다

Up Next:

github + ngrok + webhook 으로 편하게 라즈베리파이 코딩하기

github + ngrok + webhook 으로 편하게 라즈베리파이 코딩하기