[Python] 프로그래머스 lv.3 네트워크

예제 #2 : 아래와 같이 1개의 네트워크가 있습니다.

 

 

 

문제분석

• 연결된 컴퓨터는 같은 네트워크상에 있음
• 컴퓨터 n개
• 연결에 대한 정보가 담긴 2차원 배열 computers
• 네트워크 갯수 return

 

코드 설계

• dfs( )
• 연결된 값에 대해 끝까지 어디까지 연결되어있는지 확인하고 : dfs
• 더 이상 연결이 없으면 answer += 1
• computers[i][i]는 자기 자신임으로 1
• 뒷 배열은 이전에 확인을 했으면 검사할 필요 x
• dfs(
• for (int i = 0 ; i < len(computers) ; i++)
• for (int j = i ; j < len(computers) ; j++)
• 만약 computers[ i ] [ j ] == 1이면
• dfs(i,j) : 

실패..

 

정답 코드

다른 사람 코드 1 - dfs (1)

• 구하려는 네트워크 갯수는 트리의 갯수와 같다.
• 한 노드에서 탐색을 시작해 최대한 방문한 것을 1개의 트리로 계산

def solution(n, computers): # n:컴퓨터의 개수
    answer = 0
    v = [False for _ in range(n)] # 방문여부 확인
    for com in range(n) : # 컴퓨터 갯수만큼 반복
        if v[com] == False : # 만약 아직 방문하지 않은 컴퓨터라면
            dfs(n, computers, com, v) # 해당 컴퓨터, 방문 list, 현재 컴퓨터, 방문 여부
            answer += 1 # 탐색 끝났으면 anwer += 1
    return answer

def dfs(n, computers, com, v) :
    v[com] = True # 해당 컴퓨터에 방문 했음을 표시
    for connect in range(n) : # 컴퓨터만큼 반복하면서 : 다른 컴퓨터들과의 연결 비교를 위해
        if connect != com and computers[com][connect] == 1 : # 자기자신이 아니면서, [자신][다른 컴] 연결되어있다면
            if v[connect] == False : # 연결되어있는 다른 컴퓨터에 대해 dfs
                dfs(n, computers, connect, v)

 

다른 사람 코드 2 - bfs (1)

def solution(n, computers):
    answer = 0
    v = [False for _ in range(n)]
    for com in range(n):
        if v[com] == False:
            bfs(n, computers, com, v)
            answer += 1
    return answer

def bfs(n, computers, com, v):
    v[com] = True
    queue = []
    queue.append(com) # 현위치의 컴퓨터 넣고
    while len(queue != 0): # 큐에 아무것도 없을 때까지 검사
        com = queue.pop(0) # 빼서 검사
        v[com] = True
        for connect in range(n):
            if connect != com and computers[com][connect] == 1: # 현재 컴퓨터가 아니고, 연결외 되어있다면
                if v[connect] == False : # 만약 아직 검사하지 않았다면
                    queue.append(connect)

 

다른 사람 코드 3 - bfs (2)

from collections import deque

def solution(n, computers) :
    def bfs(i) :
        q = deque()
        q.append(i)
        while q : 
            i = q.popleft()
            v[i] = True
            
            for a in range(n) : 
                if computers[i][a] and not v[a] : 
                    q.append(a)
    answer = 0
    v = [False for _ in range(n)]
    for i in range(n) : 
        if not v[i] : # 방문하지 않았다면
            bfs(i)
            answer += 1
    return answer

 

2차 시도 - 2024.12.18