네트워크

* 백준 2606 바이러스

문제이해
컴퓨터의개수 : n
컴퓨터간 연결정보 : computers
연결정보로 네트워크 수 출력

dfs

1. visited 배열만들어서 모든배열의 숫자가 1이 되면 모든 컴퓨터를 다방문 ->네트워크수구할수 있음

2. visited[i] = 0인 i에서 dfs 돌릴때 네트워크개수 +1

 

def solution(n, computers):
    edges = [[0]*(n+1) for _ in range(n+1)]
    visited = [0]*(n)
    visited = [1]+visited
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if computers[i][j] == 1:
                edges[i+1][j+1] = 1

    cnt = 0
    while 0 in visited:
        cnt+= 1
        s = 0
        for i in range(len(visited)):
            if visited[i] == 0:
                s = i

        stack = [s]
        visited[s] = 1
        while stack:
            top = stack[-1]
            for i in range(n+1):
                if edges[top][i] == 1 and visited[i] == 0:
                    stack.append(i)
                    visited[i] = 1
                    break
            else:
                stack.pop()
    return cnt
    
---------------------------------------------------------------
#최근풀이
    
def solution(n,computers):
    visited = [1]+[0]*(n)
    networkcnt = 0
    computers.insert(0,[0,0,0])
    for row in computers:
        row.insert(0,0)
    # return computers 정점연결정보 인접배열생성

    def dfs(start):
        visited[start] = 1
        stack = [start]
        while stack:
            top = stack[-1]
            for k in range(n+1):
                if k == top:
                    continue
                if computers[top][k] == 1 and visited[k] == 0:
                    stack.append(k)
                    visited[k] = 1
                    break
            else:
                stack.pop()

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

    return networkcnt


n = 3
computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
# 2
# 1에서 출발해서 2담고 2애서 더 갈곳없으면
# 네트워크수 하나 세고 다음 visited가 0인 곳에서
# 다시 dfs돌리기
# visited가 0이없을때 까지 과정반복
print(solution(n,computers))