[python] 백준 2606 번 바이러스

백준 2606 번 바이러스
https://www.acmicpc.net/problem/2606

문제

참조 : 백준 2606번 DFS와 BFS
이 문제 풀고 다시 DFS 복기 하기 좋은 문제, 바이러스

풀이

이 역시 간선리스트를 인접리스트로 변환하고 v에 1을 넣었을 때 반환되는 v의 len

import sys
sys.setrecursionlimit(10000)
from collections import deque

node = int(input())
edge = int(input())
edge_list = []

for _ in range(edge):
    edge_list.append(map(int, input().split()))

graph = [[] for _ in range(node + 1)]

for v1, v2 in edge_list:
    graph[v1].append(v2)
    graph[v2].append(v1)

visited = [False] * (node + 1)

queue = deque()

def dfs (visited, v, graph):
    visited[v] = True
    queue.append(v)
    for i in graph[v]:
        if not visited[i]:
            dfs (visited, i, graph)

dfs(visited, 1, graph)
print(len(queue) - 1)

📌 주의

• 일단 인접 리스트 -> 간접 리스트 변환법 까먹지 말기. for v1, v2 in edge_list: graph[v1].append(v2) graph[v2].append(v1)
• 그리고 visited 는 0 번째 안치니까 node + 1 개의 false 가 있어야 함. 이거 까먹어서 런타임 에러 걸림...
• visited[v] = True 는 for 문 밖에 있어야 한다.