[백준/Python]2606: 바이러스

문제

https://www.acmicpc.net/problem/2606
백준 단계별로 풀어보기 - 그래프와 순회

---

풀이

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

 

컴퓨터 == 노드로 생각하고, 1번 노드와 연결되어 있는 노드의 갯수를 구한다.

DFS, BFS 모두 선택 가능한 문제다.

 

먼저 빈 리스트가 포함된 2차원 리스트를 생성한다음, 주어진 노드들을 양방향으로 저장한다.
직접 연결된 컴퓨터끼리만 영향을 주는게 아니고, 1번 컴퓨터로부터 파생된 모든 컴퓨터들은 모두 감염되는것이기 때문이다.

network = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    network[u].append(v)
    network[v].append(u)

 

ex) 단방향일경우, 만약 예제1에서 2 3이 3 2로 변경된다면?

https://www.acmicpc.net/board/view/9978

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

단방향으로 저장 시 2번 노드와 연결된 노드가 없다고 판단되므로 3번 컴퓨터가 배제된다.

 

 

그리고 방문한 노드들을 체크해야하므로 N+1만큼의 리스트를 생성한다.

visited = [False] * (N+1)

대부분의 문제에서 노드번호는 1부터 부여되므로 N+1로 맞춰주는게 편하다. (이 문제 역시 그러하다.)

 

마지막으로 DFS를 통해 노드들의 갯수를 구한 뒤, -1한 값을 출력한다.
1번 컴퓨터는 숙주이므로 감염 대상에서 제외된다.

 

 

전체 코드

# 그래프와 순회

# 1번 컴퓨터를 통해 감염된 컴퓨터의 갯수를 출력.
# 메모리: 31120KB / 시간: 32ms

from sys import stdin


input = stdin.readline
N, M = int(input()), int(input())
network = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    network[u].append(v)
    network[v].append(u)

visited = [False] * (N+1)

def checking():
    stack = [1]

    while stack:
        c = stack.pop()
        if not visited[c]:
            visited[c] = True
            for v in network[c]:
                if not visited[v]:
                    stack.append(v)

    return sum(visited) - 1  # 1번 컴퓨터는 결과에서 제외해야함.

print(checking())

 

DFS, BFS 연습문제다. 알고리즘 수업 24479~ 다음에 바로 위치한 문제인데, 이때만 해도 'DFS, BFS가 정확히 뭐지 + 어떻게 구현하는거지? + 왜 이렇게 구현하는거지??' 콤보로 헤롱헤롱했던 기억이 난다.

결론은 노드 저장 시 양방향/단방향 판단을 주의하자.