백준 2606 바이러스 파이썬 문제풀이 (python DFS BFS)

문제 보러가기

 

 

백준 바이러스 파이썬 문제풀이

이렇게 연결된 컴퓨터 그래프가 있고, 1번에 연결된 컴퓨터는 모조리 감염이다.

위 그림에서는 4,7만 감염되지 않은 것이다.

 

그래프가 연결된 것들을 탐색해내는 문제이다.

 

n = int(input())
m = int(input())
computer = [[] for _ in range(n+1)]
check = [0 for _ in range(n+1)]

def recur(num):
    check[num] = 1

    for i in computer[num]:
        if check[i] == 0:
            recur(i)

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

recur(1)
print(sum(check)-1)

이렇게 재귀를 이용해서 연결된 숫자를 방문하면서 풀었더니 틀렸다. 

왜 틀렸나.. 곰곰히 생각해보니

서로 연결되어있을 때 단방향으로 연결해놓은 것이 문제였다.

즉 (1,5)로 연결되면 1에서 5로 가지만, 5에서 1로 가지는 못하는 것.

 

양방향으로 수정하자. 

 

n = int(input())
m = int(input())
computer = [[] for _ in range(n+1)]
check = [0 for _ in range(n+1)]

def recur(num):
    check[num] = 1

    for i in computer[num]:
        if check[i] == 0:
            recur(i)

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

recur(1)
print(sum(check)-1)

a에 b를 넣었고,

밑에서 반대 방향 b에 a를 넣는 과정도 해주니

 

정답이다!