첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
1
2
3
4
5
| import sys
N = int(sys.stdin.readline())
pair = int(sys.stdin.readline())
connected = [[] for _ in range(N+1)]
|
연결되어 있는 경우
connected 배열에 연결된 index 를 append 한다!
1
2
3
4
| for _ in range(pair):
a, b = map(int, sys.stdin.readline().split())
connected[a].append(b)
connected[b].append(a)
|
DFS
- 전달된 인자를
visited = True 설정하고,
- 해당 인자를 connected의 index로 설정하여 연결된 컴퓨터들을 찾는다.
- 이 때, 연결된 컴퓨터가
not visited 일 경우 재귀 호출
1
2
3
4
5
6
7
8
9
10
| visited = [False]*(N+1)
def dfs(now):
global count
count += 1
visited[now] = True
for next in connected[now]:
if not visited[next]:
dfs(next)
|
- 1번이 걸린 경우 이어서 걸릴 애들을 세는 것이므로
count = -1 로 초기화하고 세기 시작한다.
Output
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
1
2
| dfs(1)
sys.stdout.write(str(count))
|