💡코딩테스트/프로그래머스
[프로그래머스 | 파이썬 python] 네트워크
두_두
2023. 5. 16. 16:46
깊이/너비 우선 탐색(DFS/BFS) | Find-UNION
🌏 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
👽 풀이 ➡️ find-union 이용
def solution(n, computers):
def find_parent(parent, a):
if parent[a] != a:
parent[a] = find_parent(parent, parent[a])
return parent[a]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
parent = [i for i in range(n)]
for i in range(n):
for j in range(i, n):
if computers[i][j] == 1:
union_parent(parent, i, j)
for i in range(n):
parent[i] = find_parent(parent, i)
return len(set(parent))
👽 풀이 ➡️ BFS 이용
from collections import deque
def solution(n, computers):
answer = 0
visited = [False for _ in range(n)]
def bfs(com):
visited[com] = True
queue = deque([])
queue.append(com)
while queue:
com = queue.popleft()
visited[com] = True
for connect in range(n):
if connect != com and computers[com][connect] == 1:
if visited[connect] == False:
queue.append(connect)
for com in range(n):
if visited[com] == False:
bfs(com)
answer += 1
return answer
728x90