2606 - 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

dfs -> 재귀를 통해 사용 dfs를 구현해 바이러스 문제를 풀 수 있다!

dfs는 인접리스트를 작성한다는 것만 알면 쉽게 구현할 수 있다.

 

몰랐던 부분

list_ = [[0]*(n+1) for _ in range(n+1)]에서,

2차원 list설정시 list_ = [[0]*(n+1)]*(n+1)을 하면 각각을 객체로 인식해 list_[1][2]=1을 했을 때 모든 행의 1,2 인덱스를 1로 변환하는 문제가 발생

=> for _ in range(n+1)을 통해서 정의해주며 객체로 인식하지 않게 하여 인접리스트 작성시 어려움이 없어진다.

n = int(input())
m = int(input())

#list_ = [[0]*(n+1)]*(n+1)#인접리스트
#객체로 인식 되어 리스트 구현이 힘듦.
list_ = [[0]*(n+1) for _ in range(n+1)]
check =[0]*(n+1)

for i in range(0,m):
    a,b = map(int,input().split())
    list_[a][b]=1
    list_[b][a]=1
    

check[1]=1

def dfs(temp):
    for i in range(1,n+1):
        if list_[temp][i]==1 and check[i]!=1:
            check[i]=1
            dfs(i)
    return        
    

for i in range (2,n+1):
    if list_[1][i]==1 and check[i]!=1:
        check[i]=1
        dfs(i)

cnt=0
for i in range(2,n+1):
    if check[i]==1:
        cnt+=1

print(cnt)

---

c와 python 둘다 사용함