[BFS/DFS] 백준 2606 바이러스

문제링크 www.acmicpc.net/problem/2606

[답코드]

import sys
from collections import deque
input=sys.stdin.readline
 
def bfs():
    q=deque()
    q.append(1)
    visited[1]=True
    global result
 
    while q:
        v=q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i]=True
                result+=1
 
 
 
n=int(input())
graph=[[] for _ in range(n+1)]
 
 
for _ in range(int(input())):
    a, b = map(int, input().split())
    #양방향 노드 주의
    graph[a].append(b)
    graph[b].append(a)
 
visited=[False]*(n+1)
result=0
bfs()
 
print(result)

 

[풀이법]

처음에 단방향 그래프이든 양방향 그래프이든 차이가 없다고 생각하고 29번째 줄을 넣지 않아서 틀렸다

양방향 그래프일 때 1번이 감염되면 2, 3, 4, 5 모두 감염돼 답이 4개 나오지만

단방향 그래프로 하면 1번이 감염되면 2번만 감염돼 답이 1이 나오게 된다

 

입력 예시	출력 예시
7 6 1 2 2 3 1 5 5 2 5 6 4 7	4
5 4 5 2 4 2 3 2 1 2	4
10 7 1 2 2 3 3 4 5 6 7 8 8 9 9 1	6
7 6 2 3 5 2 5 6 4 7 1 2 1 5	4