[백준][그래프] - 2606. 바이러스

[다시 푸는 문제]

[DFS]

def DFS(start):
    global answer
    visited[start] = 1
    for i in network[start]:
        if visited[i] == 0:
            DFS(i)
            answer += 1

if __name__ == "__main__":
    computer = int(input())
    pair_Computer = int(input())

    network = [[] for _ in range(computer+1)]
    visited = [0] * (computer + 1)
    answer = 0

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

    DFS(1)
    print(answer)

 

[BFS]

import collections

def BFS(start):
    global answer
    q = collections.deque([1])
    while q:
        x = q.popleft()
        visited[x] = 1

        for i in network[x]:
            if visited[i] == 0:
                q.append(i)
                visited[i] = 1
                answer += 1

if __name__ == "__main__":
    computer = int(input())
    pair_Computer = int(input())

    network = [[] for _ in range(computer+1)]
    visited = [0] * (computer + 1)
    answer = 0

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

    BFS(1)
    print(answer)

 

[메모]

• 전역 변수를 사용해서 방문 노드를 방문처리 후 answer + 1 해준 뒤 마지막에 print해준다.
• DFS는 재귀이기 때문에 따로 반복문 내에서 방문처리하지 않아도 된다.
• BFS는 재귀가 아니기 때문에 방문처리를 신경써서 해주어야 한다.