프로그래머스 - LV3. 네트워크

문제

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

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

 

내 풀이

1) BFS 이용

from collections import deque

def solution(n, computers):
    answer = n
    
    gp = [[] for _ in range(n)]
    for i in range(len(computers)):
        for j in range(0, i):
            if computers[i][j] == 1:
                gp[i].append(j)
                gp[j].append(i)
    
    visited = [0 for _ in range(n)]
    visited[0] = 1
    queue = deque([0])
    for i in range(len(visited)):
        while queue:
            node = queue.popleft()
            for i in gp[node]:
                if not visited[i]:
                    visited[i] = 1
                    queue.append(i)
                    answer -= 1
        if 0 in visited:
            queue.append(visited.index(0))
        else:
            return answer
                    
    return answer

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2) BFS 이용

from collections import deque

def solution(n, computers):
    answer = n
    
    gp = [[] for _ in range(n)]
    for i in range(len(computers)):
        for j in range(0, i):
            if computers[i][j] == 1:
                gp[i].append(j)
                gp[j].append(i)
                
    visited = [0 for _ in range(n)]
    queue = deque([])
    while 0 in visited:
        queue.append(visited.index(0))
        while queue:
            node = queue.popleft()
            visited[node] = 1
            for i in gp[node]:
                if not visited[i]:
                    visited[i] = 1
                    queue.append(i)
                    answer -= 1
                    
    return answer

위 코드에서 queue와 visited 초기화 코드를 다르게 하니 테스트 코드도 통과하였다.

 

 

 

 

 

 

 

 

 

 

 

 

 

다른 풀이

def solution(n, computers):
    answer = 0
    bfs = []
    visited = [0]*n

    while 0 in visited:
        bfs.append(visited.index(0))
        while bfs:
            node = bfs.pop(0)
            visited[node] = 1
            for i in range(n):
                if visited[i] == 0 and computers[node][i] == 1:
                    bfs.append(i)
        answer += 1
    return answer