코딩테스트/백준
[백준] 2606번 바이러스 / 파이썬(python)
Jiwon_C
2021. 5. 18. 15:39
# 문제 링크
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
# Soultion
DFS를 이용하여 푼 문제이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
n = int(input())
m = int(input())
graph = [[]*n for _ in range(n+1)]
for _ in range(m):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
cnt = 0
visited = [0]*(n+1)
def dfs(start):
global cnt
visited[start] = 1
for i in graph[start]:
if visited[i]==0:
dfs(i)
cnt +=1
dfs(1)
print(cnt)
|
cs |
3. 경로를 저장하기 위한 2차원 리스트
4. 총 m개의 간선을 입력받아 경로를 변수graph에 저장한다.
9. 다녀간 정점을 확인하기 위한 변수
15. 들리지않은 정점이면 dfs()를 이용하여 다시 반복