DFS/BFS - 네트워크

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

dfs중심으로 만들어보았다. 하지만 여기서 어떻게 답을 이끌어낼까 고민을 하는 중..

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ') #graph[v]가 아니다
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

def solution(n, computers):
    answer = 0
    n = len(computers)

    graph = [[] for _ in range(n+1)] # 그래프 생성
    
    for i in range(n):
        for j in range(n):
            if i!= j and computers[i][j]:
                graph[i+1].append(j+1)
    visited = [False] * (n+1)
    dfs(graph, 1, visited)    

    return answer

탐색한 경로는 다음과 같다 근데 내가 원하는건 탐색경로가 아닌 이어진거냐 아니냐인데... 이걸 어떻게 활용할수가 없을까..
일단 output은 네트워크 대역을 계산하는거니까 연결되지 않은 것들만 전체 컴퓨터 개수에서 빼면 나오지 않나..

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
        
def solution(n, computers):
    answer = 0
    n = len(computers)

    graph = [[] for _ in range(n+1)] # 그래프 생성
    
    for i in range(n):
        for j in range(n):
            if i!= j and computers[i][j]:
                graph[i+1].append(j+1)
    visited = [False] * (n+1)
    dfs(graph, 1, visited)
    
    answer = [ 1 for bol in visited if bol]
    answer = len(computers) - (len(answer)-1)
    return answer

머리가 빠개질것같다 ...... 결국 구글링의 힘을 썼다.

참고 링크

def solution(n, computers):
    answer = 0
    n = len(computers)

    visited = [False] * (n+1)
    
    def dfs(v):
        visited[v] = True
        for com in range(n):
            if not visited[com] and computers[v][com]:
                dfs(com)

    count = 0
    for i in range(n):
        if not visited[i]:
            dfs(i)
            count += 1

    return count

맞긴했는데.. 내 힘으로 푼게 아니라서 너무 찝찝하다..

그니까 처음 0번째 컴퓨터에서 연결된 네트워크들을 확인한다.
visited[0] and ~ 하기도 전에 visited[0] 은 이미 지나갔으니 패스
visited[1] and computers[0][1] => dfs(1)
=> visited[1] = True => visited[2] and computers[2][1] => dfs(2) => visited[2] = True => None => dfs(2) 완료 (여기서 count 가 1 증가)=> visited[2] and computers[2][2] => dfs(2) 완료 => count 1 증가..?

DFS로 최대한 탐색하고 빠져나가면 그것이 하나의 네트워크라고 한다.

조금 더 찾아보니 아까 dfs 코드로 짠거랑 비슷한 코드가 있어서 다시 한번 써본다.

참고한 링크

def dfs(computers, visited, n, com):
    visited[com] = True
    for c in range(n):
        if c != com and computers[com][c] == 1:
            if not visited[c]:
                dfs(computers, visited, n, c)

def solution(n, computers):
    answer = 0
    n = len(computers)
    visited = [False] * (n+1)
    count = 0
    
    for i in range(n):
        if not visited[i]:
            dfs(computers, visited, n, i)
            count += 1

    return count
    

굳이 그래프를 따로 만드려고 고군분투하지 않아도 된다.. .그냥 있는거 잘 써보자. 그리고 이차원 배열 접근을 너무 어색해하지말고 ㅠㅠ