(Python/LV3) 네트워크

문제 소스: https://school.programmers.co.kr/learn/courses/30/lessons/43162

설명:

from collections import deque

def solution(n, computers):

    graph = (() for _ in range(n+1))
    visited = (False) *(n+1)
    count = 0

    for idx, i in enumerate(computers):
        for j in range(len(i)):
            if computers(idx)(j) == 1 and idx != j :
                graph(idx+1).append(j+1)
                
    for i in range(1,n+1):
        if visited(i) == False:
            dfs(idx,graph,visited)
            count += 1
    return count

def dfs(start,graph,visited):
    visited(start) = True
    for e in graph(start):
        if visited(e) == False:
            dfs(e,graph,visited)
    return visited
print(solution(    3, ((1, 1, 0), (1, 1, 0), (0, 0, 1))))
# print(solution(3, ((1, 1, 0), (1, 1, 1), (0, 1, 1))))

66점 맞음

from collections import deque

def solution(n, computers):

    graph = (() for _ in range(n+1))
    visited = (False) *(n+1)
    count = 0

    for idx, i in enumerate(computers):
        for j in range(len(i)):
            if computers(idx)(j) == 1 and idx != j :
                graph(idx+1).append(j+1)



    for i in range(1,n+1):
        if visited(i) == False:
            dfs(i,graph,visited)
            count += 1
    return count

def dfs(start,graph,visited):
    visited(start) = True
    for e in graph(start):
        if visited(e) == False:
            dfs(e,graph,visited)
    return visited

맞는 것 같은데 찾아보니 전에 쓰던 idx가 중간에 있어서 idx를 i로 바꿨습니다.

위의 for 문에서 사용된 idx에 숫자 2가 포함된 이유를 모르겠습니다.

graph = (() for _ in range(n+1)) # 그래프
visited = (False) *(n+1) # 밟은 땅 확인을 위한 visited
count = 0 # 정답 count

for idx, i in enumerate(computers):
    for j in range(len(i)):
        if computers(idx)(j) == 1 and idx != j :
            graph(idx+1).append(j+1)

열거하므로 idx로 뺍니다.

cf) enumerate(computers, start = 1) 시작값이 주어지면 idx의 시작값이 변경된다.

print(solution( 3, ((1, 1, 0), (1, 1, 0), (0, 0, 1))))

위의 수식으로 하고 싶은 것은 연결된 선을 찾는 것입니다.

문을 열면 그래프(1)은 숫자 2에 연결되고 그래프(2)는 숫자 1에 연결됩니다.

for i in range(1,n+1):
    if visited(i) == False:
        dfs(i,graph,visited)
        count += 1
return count

0이 없으므로 1부터

밟지 않았다면 dfs를 실행하고 dfs를 통하고 연결이 끊겼다면 네트워크이므로 count += 1

def dfs(start,graph,visited):
    visited(start) = True
    for e in graph(start):
        if visited(e) == False:
            dfs(e,graph,visited)
    return visited

dfs 표현식