[백준] 2606 - 바이러스 (python3)

문제

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

 

 

풀이 (bfs)

from collections import deque

# 1. 입력받기
n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화

for i in range(v): # 그래프 생성
    a,b=map(int,input().split())
    graph[a]+=[b] # a에 b 연결
    graph[b]+=[a] # b에 a 연결 -> 양방향
    
#print(graph)

# 2. 노드 탐색 (bfs / 큐)
visited = [0] * (n+1) # 방문 여부 체크
visited[1]=1 # 1번 컴퓨터부터 시작이니 방문 표시
Q=deque([1])
while Q:
    c=Q.popleft() # 왼쪽에서 빼기
    for nx in graph[c]:
        if visited[nx]==0:
            Q.append(nx) #오른쪽에 추가
            visited[nx]=1

print(sum(visited)-1)

 

 

풀이 (dfs)

# 1. 입력받기
n = int(input())
v = int(input())
graph = [[] for i in range(n+1)] # 그래프 초기화

for i in range(v):
    a,b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]

#print(graph)

visited = [0] * (n+1)

# 2. dfs 함수 구현 (재귀)
def dfs(v):
    visited[v]=1

    for nx in graph[v]:
        if visited[nx]==0:
            dfs(nx)
        #print(f"v={v} | nx={nx} | {visited}")

# 3. 노드 탐색 (dfs / 재귀)
dfs(1)
#print(visited)
print(sum(visited) -1)

 

 

출처

https://bio-info.tistory.com/152

[백준] 2606 바이러스 - Python (그래프 탐색)