[백준/파이썬] 2606 바이러스

#문제링크

https://www.acmicpc.net/problem/2606

2606번: 바이러스

#나의풀이

import sys
sys.setrecursionlimit(10**6)

def DFS(x):
    ch[x] = 1
    for i in range(1, N+1):
        if board[x][i] == 1 and ch[i] == 0:
            DFS(i)
        board[x][i] = 0
    return True

if __name__ == '__main__':
    N = int(sys.stdin.readline())
    T = int(sys.stdin.readline())
    board = [[0] * (N+1) for _ in range((N+1))]
    ch = [0] * (N+1)

    for _ in range(T):
        a, b = map(int, sys.stdin.readline().split())
        board[a][b] = 1
        board[b][a] = 1
    DFS(1)

    print(sum(ch)-1)

#해설

풀이는 여러가지가 있을꺼 같은데 접근은 DFS로 했다.

값들을 입력받고 전염이 되었는지 확인하기 위해 ch배열을 만들었다 마지막에 sum 함수로 1의 개수를 세서 출력해줄것이다.

반복문으로 입력받을때 한방향으로만 하면 될 줄 알았는데 반례가 존재한다. 연결이 1이고 2 1을 입력받을때 DFS(1)을 했을경우 0으로 값이 나오는데 a b와 b a로 양방향으로 체크해줘야한다.

이후 DFS로 값을 돌게되고 그 수와 연결이 되어있고 체크가 안되어있다면 다시 DFS로 돌게된다. 이후 값을 0으로 바꿔주어 다시 돌지 않게 방지해준다.