[프로그래머스-DFS/BFS] 네트워크_파이썬 ❌❌

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

---

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    for i in range(n):
        if visited[i] == False:
            dfs(n, computers, visited, i)
            answer += 1
    
    return answer

def dfs(n, computers, visited, i):
    visited[i] = True
    
    for j in range(n):
        if computers[i][j] == 1 and i != j:
            if visited[j] == False:
                dfs(n, computers, visited, j)

방문하지 않은 노드가 있다면, dfs를 이용해 연결되어있는 모든 노드를 방문하고 answer += 1

---

def solution(n, computers):
    def dfs(n, computers, start):
        stack = [start]
        
        while stack:
            i = stack.pop()
            visited[i] = True
            
            for j in range(n):
                if computers[i][j] == 1 and i != j:
                    if visited[j] == False:
                        stack.append(j)
                        
    visited = [False] * n
    answer = 0
    
    for i in range(n):
        if visited[i] == False:
            dfs(n, computers, i)
            answer += 1
    
    return answer

반복문을 활용한 dfs 풀이. 재귀와 비교하여 직관적이다.

---

def solution(n, computers):
    temp = [i for i in range(n)]
    
    for i in range(n):
        for j in range(n):
            if computers[i][j]:
                for k in range(n):
                    if temp[k] == temp[i]:
                        temp[k] = temp[j]
    
    return len(set(temp))

플로이드 워셜 알고리즘을 이용한 풀이. 노드가 연결되어있다면 같은 수로 만들어준다.

최종적으로 집합자료형을 이용해 중복을 제외한 개수(temp 길이)가 네트위크 개수가 된다.