[백준 2606] 바이러스

0. 제목

• 백준 2606 바이러스
• BOJ 2606 바이러스
• 파이썬 2606 바이러스
• Python 2606 바이러스

---

1. 문제

www.acmicpc.net/problem/2606

2606번: 바이러스

---

2. 풀이

• adj라는 2차원 배열 형태를 선언한 후, 각 점의 연결 상태를 표시한다. adj[2] = [1, 3, 4] 라면 2번에 1번, 3번, 4번이 연결되어 있다는 것이다.
• visited라는 1차원 배열을 선언한 후, 각 점에 대한 방문 여부를 표시한다. visited[3] = True 라면 3번 점에 이미 방문했다는 것을 의미한다.
• 문제에서는 1번 점을 통해 탐색할 수 있는 점의 개수를 구하라고 하였고 dfs를 활용하면 된다.
• 특정 점에서 출발하여 지나는 갯수를 셀 수 있는 함수를 만든다. 방문한 점에 대하여 visited[방문한 점] = True 를 수행하고, 인접한 점중 방문하지 않은 점에 대하여 재귀적으로 함수를 수행한다.
• 전역변수로 선언한 count를 점을 방문할 때마다 1 증가시킴으로써 정답을 구한다.
• 마지막에 시작점을 제외해야 하기 때문에 count에서 1을 뺀다.

---

3. 코드

n = int(input())
m = int(input())
 
adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
count = 0
 
for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
    
def dfs(now_pos):
    global count
    count += 1
    visited[now_pos] = True
    for next_pos in adj[now_pos]:
        if not visited[next_pos]:
            dfs(next_pos)
    
dfs(1)
print(count - 1)