[프로그래머스] (Python) - 네트워크

문제링크

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

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

 

 

풀이 

 

1. 0번 컴퓨터부터 연결된 모든 컴퓨터를 방문한다. (재 방문 하지 않기 위해 g_check이라는 배열에 방문체크를 한다.)

-> 연결된 모든 컴퓨터를 방문하고 나면 answer += 1을 해준다. (연결 컴퓨터를 모두 방문하면 네트워크 한덩어리 발견!)

2. 방문체크는 DFS를 이용하여  재귀적으로 구현했다.

 

 

g_check = []
g_computers = []

def solution(n, computers):
    answer = 0
    global g_check, g_computers
    g_computers = computers
    g_check = [False for i in range(n)] # 방문 체크할 check 배열
    for j in range(n):
        if g_check[j] == False:
            dfs(j) # dfs를 호출하여 j번째 컴퓨터와 연결된 모든 컴퓨터 방문처리
            answer += 1 # 연결된 컴퓨터를 방문처리하고나면 네트워크 한 뭉치 += 1
    return answer

def dfs(j):
    global g_check
    if g_check[j] == True: # 이미 방문한 컴퓨터라면 종료
        return
    g_check[j] = True
    for (idx, v) in enumerate(g_computers[j]):
        if v == 1:
            if g_check[idx] == False: # 배열 값이 1이고(연결 되었고), 아직 방문하지 않았다면 
                dfs(idx)