[프로그래머스] 네트워크 (플로이드-워셜, DFS)

사용 언어: Python3

문제

네트워크

내 풀이 - 플로이드-워셜 이용

from collections import Counter
def solution(n, computers):
    # ✅ 플로이드-워셜
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if computers[i][k] == 1 and computers[k][j] == 1:
                    computers[i][j] = 1
                    
    visited = [0] * n
    cnt = 0 
    for i in range(n):
        if visited[i]: # ✅ 이미 방문한 노드라면 패스
            continue
        for j in range(n):
            if computers[i][j]:
                visited[j] = 1
        cnt += 1
    return cnt

• 성공

다른 풀이 - DFS

참고

def solution(n, computers):
    def DFS(L):
        visited[L] = 1
        for nei in range(n): # 인접노드 탐색
            if computers[L][nei] == 0 or visited[nei]:
                continue
            DFS(nei)
    
    visited = [0] * n
    cnt = 0
    for i in range(n):
        if visited[i]:
            continue
        DFS(i)
        cnt += 1
    
    return cnt

• 성공!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기