[Baekjoon] 2606 Python

2606번: 바이러스

 

예제 입력 1

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

예제 출력 1

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

 

풀이과정

기본적인 dfs문제였지만 처음에 접했을 때는 바로 풀지 못했다. 다른 촌수계산 문제들을 풀다가 다시 돌아와 풀어보니 그래도 쉽게 풀렸던 문제. 연결되어 있는 컴퓨터들을 각 인덱스에 넣어주고 dfs로 탐색하면서 방문했던 노드는 제외하면서 카운트해주었다. 

1. 전체 컴퓨터 개수(N)에 맞게 nums 리스트와 visited를 만들어둔다. 이때 인덱스 0은 비워지게 되므로 N+1의 길이로 만들어줘야 한다. 
visited는 연결된 컴퓨터를 오가며 연결성을 확인할 때 이미 방문한 노드인지 아니지 확인해주기 위해서 필요하다.

2. for문을 돌리면 각 인덱스에 값을 넣어준다. 양방향으로 넣어주기 때문에 아래와 같이 담긴다.
    [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

3. dfs로 탐색하며 전달받은 인덱스의 visited를 True로 바꿔주어 방문했던 것을 체크하고, nums의 해당 인덱스의 값들을 반복하여 dfs탐색해준다. 방문한 적이 없다면 count +=1 해준다. 

import sys;

input = sys.stdin.readline

N = int(input())
K = int(input())
nums = [[] for _ in range(N + 1)]	# [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
visited = [False] * (N + 1)		# [False, True, True, True, False, True, True, False]
count = 0

for i in range(K):
    a, b = map(int, input().split())
    nums[a].append(b)
    nums[b].append(a)


def dfs(a):
    global count
    visited[a] = True
    for i in nums[a]:
        if not visited[i]:
            count += 1
            dfs(i)


dfs(1)
print(count)