[프로그래머스 | BFS/DFS] 네트워크, Python
🏆 BFS
def solution(n, computers):
answer = 0
from collections import deque
network = deque()
for i in range(n):
if computers[i][i] == 1:
network.append(i)
while network:
root = network.popleft() # BFS on root
computers[root][root] = 0 # Myself - mark as 0, do not seek this node any more
for idx, connected in enumerate(computers[root]):
if connected==1:
network.append(idx) # Append connected computer on deque
computers[root][idx] = 0 # Mark as 0 (Visited), do not seek this node any more
computers[idx][root] = 0 # Mark as 0 (Visited), do not seek this node any more
answer += 1
return answer
def solution(n, computers):
answer = 0
from collections import deque
network = deque()
for i in range(n):
if computers[i][i] == 1:
network.append(i)
while network:
root = network.popleft() # BFS on root
computers[root][root] = 0 # Myself - mark as 0, do not seek this node any more
for idx, connected in enumerate(computers[root]):
if connected==1:
network.append(idx) # Append connected computer on deque
computers[root][idx] = 0 # Mark as 0 (Visited), do not seek this node any more
computers[idx][root] = 0 # Mark as 0 (Visited), do not seek this node any more
answer += 1
return answer전형적인 DFS/BFS 문제
방문한 노드는 0으로 표기해서 더이상 고려하지 않는게 포인트
BFS 중 더이상 방문할 노드가 없다면 (연결된 컴퓨터가 더이상 없다면), 새로운 root를 찾아 큐에 넣고 BFS 반복
Author And Source
이 문제에 관하여([프로그래머스 | BFS/DFS] 네트워크, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dd9s2/프로그래머스-네트워크-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
