[프로그래머스/Python] Level 3_네트워크(BFS)

📌문제 유형

BFS, DFS

 

📌문제

프로그래머스

 

📌나의 문제풀이

- graph 만들어서 기본적인 BFS

- 주의) j를 i+1 부터 시작하면 안 됨! 그 전에도 연결되어 있을 수 있음

from collections import deque

def solution(n, computers):
    answer = 0
    graphs = [[] for _ in range(n+1)]
    visited = [0 for _ in range(n+1)]
    
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1 and i != j:
                graphs[i+1].append(j+1)
                
    for x in range(1,n+1):
        if visited[x] == 0:
            q = deque([x])
            visited[x] = 1
            answer += 1
            
            while q:
                v = q.popleft()
                for y in graphs[v]:
                    if not visited[y]:
                        q.append(y)
                        visited[y] = 1
    
    return answer

 

 

📌다른사람의 문제풀이

def solution(n, computers):
    answer = 0

    queue = []
    visited = []

    for a in range(n):
        if a not in visited:
            queue.append(a)
            answer += 1

            while queue :
                now = queue.pop(0)    
                for i in range(n):
                    if computers[now][i] == 1 and i not in visited:
                        visited.append(i)
                        queue.append(i)
    return answer