Back/Algorithm

백준 알고리즘 2606 바이러스 / 파이썬 (Python)

백준 알고리즘 2606 바이러스 / 파이썬 (Python)

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

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어

www.acmicpc.net

N = int(input())
P = int(input())

graph = [[0]*(N+1) for _ in range(N+1)]

done = [] # 바이러스가 완료된 애들을 넣어주는구나

for _ in range(P):
    x, y = map(int, input().split())
    graph[x][y], graph[y][x] = 1,1

def dfs(v):
    done.append(v)
    for k in range(1, N+1):
        if (k not in done) and (graph[v][k] == 1):
            dfs(k)
    return (len(done) - 1)

print(dfs(1))
N = int(input())
P = int(input())

graph = [[0]*(N+1) for _ in range(N+1)]

전체 컴퓨터 수인 N 값과

총 연결값인 P값의 입력값을 받는다.

 

그 후

graph를 만든다. False, True 식의 인접행렬을 0과 1로 나타낸 것이다.

 

만들어진 graph는 리스트안에

 

[0 0 0 0 0 0 0 0],

[0 0 0 0 0 0 0 0],

[0 0 0 0 0 0 0 0],

. . . . .

 

이렇게 만들어진다.

for _ in range(P):
    x, y = map(int, input().split())
    graph[x][y], graph[y][x] = 1,1

연결된 컴퓨터의 입력값을 받는다.

 

입력값을 받을 때 마다, 만난 것들은 감염된 것들이니, 감염된 것들은,

 

위에서 만든 graph 리스트에 0을 1로 바꾸어 표기해준다.

 

이걸 좀 쉽게 이야기하면, 0~7까지, 각각 만나는 지점을 1로 바꿔준다고 생각하면 쉽다.

 

ex) 1, 2가 들어온 경우.

    0 1 2 3 4 5 6 7

0 [0 0 0 0 0 0 0 0]

1 [0 0 1 0 0 0 0 0]

2 [0 1 0 0 0 0 0 0]

3  . . . . .

 

이렇게 (1,2) 가 만나는 지점과 (2,1)이 만나는 지점이 1로 바뀌었다. 즉 감염되었다.

 

def dfs(v):
    done.append(v)
    for k in range(1, N+1):
        if (k not in done) and (graph[v][k] == 1):
            # 1.2번째는 감염이 됨
            dfs(k) #재귀함수를 통해 2
                  # 그럼 done에 2를 더하고
    return (len(done) - 1)

print(dfs(1))

 

제일 끝까지 내려가 탐색하는 DFS의 방식을 활용한다. 함수명은 아무렇게나 해도 상관없다.

 

dfs(v) 함수에 v값이 들어오면

 

v값은 위에서 정한 done 리스트에 저장해준다.

 

done은 감염된 컴퓨터 넘버를 저장해주는 리스트다.

 

그 후 for문을 통해

 

(1~8) 즉 1부터 7까지 전체 컴퓨터 수를 반복하여 감염이 되었는지 안되었는지 확인한다.

 

if

만약 done( 감염된 컴퓨터 ) 리스트에 없는데 graph에서 만나는 지점이 0이 아니라 1인 경우,

 

이 경우는 감염된 컴퓨터 리스트인 done에는 없지만 감염된 컴퓨터 이므로,

 

재귀를 이용해 다시 dfs로 보내고, done에 그 숫자를 추가한다.

 

이런 식으로 계속 재귀를 통해 1~7까지 모든 만나는 지점을 검사하고,

 

1인 경우는 done에 추가하여 done 리스트를 채운다.

 

for문과 if문을 다 통과한 후

 

done의 길이에서 1을 빼고 리턴해준다.

 

1을 빼는 이유는 처음에 감염을 퍼뜨리는 컴퓨터를 done에 포함시켰기 때문에 그 길이에서 뺴준다.