프로젝트 하느라 DFS/BFS도 까마득하다~~ 기초적인 문제부터 다시 풀자.

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1

4

나의 코드

from sys import stdin as s
from collections import deque

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n = int(s.readline())
m = int(s.readline())

graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

nodes = [[node1, node2] for node1, node2 in [
    list(map(int, s.readline().split())) for _ in range(m)]]

for node in nodes:
    graph[node[0]].append(node[1])
    # 왜 양방향 간선이어야만 하는가? 아래에 반례를 적어보았다.
    graph[node[1]].append(node[0])

visited[1] = True
## BFS로 풀이할 것이므로 queue 사용
queue = deque([1])

## 전형적인 BFS 풀이. queue에서 하나씩 꺼내서 노드를 방문한다.
while queue:
    cur = queue.popleft()
    for node in graph[cur]:
        if not visited[node]:
            visited[node] = True
            queue.append(node)

# true를 일일히 다 세고 있는데, 그냥 0과 1로 나타내서 배열의 원소를 합산하고 1을 빼는 방식으로 갔으면 더 효율적이었겠지? ㅋㅋㅋ
true_count = 0
for i in range(2, n + 1):
    if visited[i]:
        true_count += 1
print(true_count)

처음에는 단방향 간선으로만 두어도 충분하다고 생각했다.
하지만 아니었다.
양방향 간선을 다 고려해야만 하는 문제이다.

단방향 간선만 고려 시 반례

만약 문제에서 8번 컴퓨터가 추가되고, 8번이 4번 컴퓨터와 연결되어 있다고 가정하자.
이때 문제에서 입력은 이렇게 주어질 것이다.

예제 입력 1

8
7
1 2
2 3
1 5
5 2
5 6
4 7
4 8

또는

예제 입력 1

8
7
1 2
2 3
1 5
5 2
5 6
4 7
8 4

만약 전자라면 문제 없지만, 후자일 경우 문제가 된다.
입력이 8 4로 들어오게되면,
내 코드 로직 상 8번 노드는 방문할 일이 없게된다.

[[], [2, 5], [3], [], [7], [2, 6], [], [], [4]]

BFS일 경우
1 - 2 - 5 - 3 - 6

이 순서대로 방문할 텐데, 5번 노드 방문할 차례 때 2번 노드 리스트의 원소인 3과, 6을 방문하고 나면 (6번 노드 리스트의 원소는 없다.) 탐색이 종료된다. 그럼 8번 노드 리스트는 언제 방문해? 못하지.. 그래서 단방향이 아니라 양방향 간선으로 표현해 놓아야 하는것이다.