백준 / 실버 3 / 2606 바이러스 / Python [플로이드 워셜 or 완전탐색]

https://www.acmicpc.net/problem/2606

구조

1. 시간복잡도

N = 100 : O(N4) 주로 완전탐색. dfs, bfs 땡기는걸로

2. 알고리즘

dfs

3. 체크리스트

입력:

N = int(input())
E = int(input())

G = [[] for _ in range(N+1)]
for _ in range(E):
	a, b = map(int, input().split())
    G[a] += [b]
    G[b] += [a]

4. 엣지케이스

풀이

실수: 첫 for문 입력을 아무생각없이 range(N)으로 받음

import sys
input = sys.stdin.readline

N = int(input())
E = int(input())

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

for _ in range(E):
    a, b = map(int, input().split())
    G[a] += [b]
    G[b] += [a]

visited = [0] * (N+1)

def dfs(n):
    visited[n] = 1
    for m in G[n]:
        if not visited[m]:
            dfs(m)
        
dfs(1)
print(sum(visited) - 1)

리스트 덧셈으로 값 추가

l += [1] 삽가능
l.append(1)
# set.add(1)
# set.update([3,2,1])
# set |= {3,2,1}

2차원 리스트 초기화

ls = [[] for _ in range(N)]