(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)

enumerate 를 해주므로 idx와 같이 빼준다 

cf) enumerate(computers, start = 1) start 값을 지정해주면 idx의 시작값이 바뀜

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

위 식으로 하고자 하는것은 연결된 선을 찾기 위함이다

포문을 돌리면  graph[1] 에서 2번으로 연결 graph[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 식