[Python] 백준 풀기 2606 - 바이러스

파이썬 백준 2606번

실버3

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

 

 

 

문제 보기

분류: 그래프 이론, DFS

 

 

문제 풀기

작동방식은 이해를 하였으나 아직 코드 형태가 친근하지 않은 DFS 로 접근해보는 문제이다.

 

컴퓨터의 개수와 연결된 개수를 입력 받고 연결된 두 노드간의 정보를 저장하기 위한 2차원 매트릭스를 작성한다.

그리고 컴퓨터의 개수보다 1개 더 많게 0으로 채워진 visited_dfs 를 만든다. (index 번호와 컴퓨터의 번호를 맞추기 위한 +1 개)

for loop 으로 모든 컴퓨터 연결들을 매트릭스에 저장한다. 이 매트릭스는 대칭을 이룬다.

 

컴퓨터 1번 부터 시작하기에 dfs(1) 로 함수를 실행한다.

방문이 된 visited_dfs[index] 에는 1을 저장하고, 이 선택된 컴퓨터를 중심으로 모든 컴퓨터에 대해 '방문 표시가 되어있지 않은지 그리고 컴퓨터간의 연결이 되어있는지' 를 확인하고 다시 dfs(i) 를 실행 시킨다.

    for i in range(1, computer + 1):
        if(visited_dfs[i] == 0 and matrix[V][i] == 1):
            dfs(i)

 

모든 컴퓨터에 방문이 이루어 졌거나 방문이 할 곳이 없게 되면 함수는 종료된다.

리스트 visited_dfs 안에 들어있는 1의 개수를 찾고 그 개수에서 -1 을 하여 출력한다. (-1 은 처음 1번 컴퓨터임)

 

코드에는 순차적으로 방문이 이루어진 컴퓨터의 수와 연결이 저장된 매트릭스의 프린트 결과가 추가되었다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def dfs(V):
    visited_dfs[V] = 1
    print(V, end = ' ')
    
    for i in range(1, computer + 1):
        if(visited_dfs[i] == 0 and matrix[V][i] == 1):
            dfs(i)
    

if __name__ == "__main__":
    computer = int(inputdata().strip())
    linked = int(inputdata().strip())
    matrix = [[0] * (computer + 1) for _ in range(computer + 1)]
    visited_dfs = [0] * (computer + 1)
    for i in range(linked):
        a, b = map(int, inputdata().split())
        matrix[a][b] = matrix[b][a] = 1

    dfs(1)
    print(matrix)
    print(visited_dfs.count(1) - 1)



# 7
# 6
# 1 2
# 2 3
# 1 5
# 5 2
# 5 6
# 4 7


# 1 2 3 5 6 

# [
#     [0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 1, 0, 0, 1, 0, 0], 
#     [0, 1, 0, 1, 0, 1, 0, 0], 
#     [0, 0, 1, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 1], 
#     [0, 1, 1, 0, 0, 0, 1, 0], 
#     [0, 0, 0, 0, 0, 1, 0, 0], 
#     [0, 0, 0, 0, 1, 0, 0, 0]
# ]


# 4