[Python] BOJ 2606 : 바이러스

요구사항

1. 시간 제한 1초 
   1. NlogN 까지 N <= 100 
2. 메모리 제한 128MB
   1. 128 *10^6 
3. 1번 컴퓨터(노드)와 연결된 컴퓨터의 수를 출력하라

설계

1. 재귀의 깊이(10**7)을 설정한다.
2. 컴퓨터의 수 N개를 받는다.
3. 간선의 개수를 받는다.
4. 한 줄에 연결된 노드 쌍을 간선의 개수만큼 입력 받는다. 
5. DFS or BFS로 구현한다.
6. visited[boolean] 으로 True 값을 카운트
7. 1번을 통해 감염된 컴퓨터의 수니깐 True의 개수에서 - 1을 한 뒤 결과값을 출력한다. 

import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().strip()

N = int(input())

E = int(input())

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

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

def dfs(v):
    visited[v] = True
    
    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            dfs(i)
dfs(1)
print(visited.count(True) - 1)

 

+ 2024.09.26 복습, 바뀐 부분

• 기존 코드에서는 1번 컴퓨터로부터 감염된 컴퓨터의 개수를 visited의 True 여부로 검사했다.
• 하지만 아래의 소스 코드는 count 해주었다.
• 노드와 간선을 입력 받는 부분은 한 줄에 2개의 입력값을 받는다. (문제와 별개)

import sys
sys.setrecursionlimit(10**7)

input = lambda: sys.stdin.readline().rstrip()

V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]
visited = [False] * (V+1)
count = 0

for _ in range(E):
    u,v = map(int, input().split())
    graph[u].append(v)
    graph[V].append(u)

def dfs(v):
    global count
    visited[v] = True

    for i in graph[v]:
        if not visited[i]:
            count += 1
            visited[i] = True
            dfs(i)

dfs(1)
print(count)