프로그래머스 네트워크

그래프, BFS/DFS 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

💡 풀이코드 (성공 - MST Prim)

import heapq

def solution(n, computers):
    answer = 0
    
    graph = [[] for _ in range(len(computers) + 1)]
    
    # graph 만들기
    for i in range(len(computers)):
        for j in range(len(computers)):
            if i == j: continue
            
            if computers[i][j] == 1:
                graph[i + 1].append(j + 1)
    print(graph)
    
    # MST - prim
    Q = []
    visited = [False for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        if visited[i] == True: continue
        
        heapq.heappush(Q, i)

        while Q:
            v = heapq.heappop(Q)

            for nv in graph[v]:
                if visited[nv] == False:
                    visited[nv] = True 
                    heapq.heappush(Q, nv)
        answer += 1
        
        
    
    return answer

 

주요 로직

1. 그래프 생성

우선, 익숙한 2차원 양방향 그래프 형태로 만들어주었다.

i == j일 때는 자기 자신의 노드를 의미하므로, 이 경우를 제외하고 그래프에 추가해주었다.

 

2. MST Prim 알고리즘

보통의 Prim 알고리즘에서는 힙에 간선의 가중치도 같이 삽입한다.

하지만, 이 문제에서는 가중치가 필요없을 뿐더러 가중치 관련 정보도 없기 때문에 힙에 삽입을 생략했다.

 

먼저, 1에서부터 n(최대 노드값)까지 for문을 돈다.

이 반복문은 (다른 노드와 연결되어 있지 않아) 방문하지 않은 노드를 모두 순회하기 위한 목적이다.

그래프의 시작 노드를 힙에 넣어주고, 힙에 원소가 남아있을때까지 로직을 반복한다.

 

💡 풀이코드 (성공 - DFS)

def dfs(v):
    for nv in graph[v]:
        if visited[nv] == False:
            visited[nv] = True
            dfs(nv)

def solution(n, computers):
    global visited,graph
    answer = 0
    
    graph = [[] for _ in range(len(computers) + 1)]
    visited = [False for _ in range(n + 1)]
    
    
    # graph 만들기
    for i in range(len(computers)):
        for j in range(len(computers)):
            if i == j: continue
            
            if computers[i][j] == 1:
                graph[i + 1].append(j + 1)
                
    for i in range(1, n + 1):
        if visited[i] == False:
            dfs(i)
            answer += 1
    return answer