(python) 백준 2606 - 바이러스 (DFS활용)

백준 2606

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

2606번: 바이러스

 

1. 문제 설명

 

문제에서 제시된 <그림 1>처럼 그래프를 구성하여 1번 컴퓨터와 연결된 컴퓨터를 탐색하는 그래프 탐색 문제.

 

2. 문제 풀이

 

그래프를 인접행렬로 구성한다.

 

graph = [[] for _ in range(n+1)]    #인접행렬 그래프

for _ in range(m):
    a, b = map(int, input().split())    
    graph[a].append(b)  #a, b연결
    graph[b].append(a)  #a, b연결

 

1번 정점을 시작으로 DFS알고리즘으로 1번 정점과 연결된 정점들을 모두 방문한다.

 

def dfs(s):
    global cnt
    visited[s] = 1	#정점s에 대해 방문체크
    for i in graph[s]:
        if visited[i] == 0: #미방문여부 확인
            dfs(i)  #방금 방문한 정점에 대하여 dfs수행
            cnt += 1

 

깊이우선탐색(DFS) 참고 링크: https://michelangeloo.tistory.com/5

(python) 그래프 순회 - 깊이 우선 탐색(DFS) (Feat. 백준 11403)

 

3. 전체 코드

 

def dfs(s):
    global cnt
    visited[s] = 1
    for i in graph[s]:
        if visited[i] == 0: #미방문 확인
            dfs(i)  #방금 방문한 정점에 대하여 dfs수행
            cnt += 1

n = int(input())    #컴퓨터 수
m = int(input())    #번호 쌍 수

graph = [[] for _ in range(n+1)]    #인접행렬 그래프

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  #a, b연결
    graph[b].append(a)  #a, b연결
    
visited = [0 for _ in range(n+1)]   #방문여부 체크
cnt = 0
dfs(1)
print(cnt)