코딩 테스트 연습 '네트워크' 문제 풀이

코딩 테스트 연습 '네트워크' 문제 풀이

문제

https://programmers.co.kr/learn/courses/30/lessons/43162?language=python3

문제에서 computers가 인접 행렬로 주어지고 이를 활용하여 dfs나 bfs를 진행합니다.

더 이상 탐색이 진행되지 않으면 기존 네트워크 수에 +1을 합니다.

인접 행렬 dfs, bfs

https://lbdiaryl.tistory.com/173?category=1010228

같은 유형의 문제

https://lbdiaryl.tistory.com/171?category=1028082

문제 풀이(dfs)

def solution(n, computers): def dfs(v): for k in range(len(computers)): if computers[v][k] == 1: computers[v][k]=0 dfs(k) Count=0 for i in range(n): for j in range(len(computers[i])): if computers[i][j]==1: dfs(i) Count+=1 return Count

문제 풀이(bfs)

from collections import deque def solution(n, computers): def bfs(start): queue = deque([start]) while queue: v=queue.popleft() for k in range(len(computers[start])): if computers[v][k]==1: queue.append(k) computers[v][k]=0 Count=0 for i in range(n): for j in range(len(computers[i])): if computers[i][j]==1: bfs(i) Count+=1 return Count

from http://lbdiaryl.tistory.com/214 by ccl(A) rewrite - 2021-11-25 15:01:42