2022.02.14 [백준] (python 파이썬) 바이러스

 

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

2606번: 바이러스

---

풀이

이 문제는 최단거리나 방향성이 있는 문제가 아니기 때문에 bfs와 dfs를 모두 사용할 수 있다.

 

아래의 코드는 bfs를 이용하여 작성한 코드이다.

graph배열을 생성 후, 각 정점에서 연결된 정점들을 저장한다.

그리고 vis배열을 이용하여 각 정점에 방문했는지의 여부를 체크한다.

from collections import deque
 
n=int(input())
m=int(input())
graph=[[]*n for _ in range(n+1)]
vis=[-1]*(n+1)
 
def bfs(i):
    deq=deque()
    deq.append(i)
    vis[i]=0
    cnt=0
    while deq:
        v=deq.popleft()
        cnt += 1
        for i in graph[v]:
            if vis[i]==-1:
                deq.append(i)
                vis[i]=0
    return cnt-1
 
for _ in range(m):
    a,b=map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
print(bfs(1))

 

아래의 코드는 dfs로 작성한 코드이다.

from collections import deque
 
n=int(input())
m=int(input())
graph=[[]*n for _ in range(n+1)]
vis=[-1]*(n+1)
cnt=0
def dfs(i):
    vis[i]=0
    global cnt
    cnt+=1
    for a in graph[i]:
        if vis[a]==-1:
            dfs(a)
 
for _ in range(m):
    a,b=map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
dfs(1)
print(cnt-1)