백준 2606번 : 바이러스
난이도 : 실버 3
- 문제 소개
- 조건
- 없음
- 코드
import sys
from collections import deque
input = sys.stdin.readline
C = int(input())
V = int(input())
graph = [[] for _ in range(C+1)]
for _ in range(V):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
ch = [0] * (C + 1)
path = []
def dfs(v):
for nv in graph[v]:
if ch[nv] == 0:
path.append(nv)
ch[nv] = 1
dfs(nv)
ch[1] = 1
dfs(1)
print(len(path))
- 해설
DFS를 통해 깊이 우선 탐색을 진행했습니다. 코드는 크게 세 부분으로 나누어서 설명할 수 있습니다.
C, V를 입력받고 graph를 만들어서 양방향 그래프를 입력받고, 체크하는 배열 ch와 경로 체크를 위한 path 배열을 만들어준 setting파트, dfs 함수를 만들어 깊이 우선 탐색을 진행하는 파트, 마지막으로 1을 입력값으로 하여 함수를 진행시키고 출력값을 내는 출력파트입니다.
setting 파트를 보자면 sys 모듈에서 stdin.readline을 불러와 그냥 input()함수보다 빠른 입력 처리를 위해 input을 재정의해주었습니다. 그리고 파이썬에서 queue를 쓰기 위해서 필요한 deque 모듈도 불러왔습니다.
컴퓨터의 개수(정점) C와 네트워크의 개수(간선) V를 입력받아주고, 이차원 리스트 graph를 (C+1) * (C+1)개 만들어주었습니다. 이유는 인덱스를 입력값(컴퓨터)과 맞추어주기 위해서입니다. 간선의 개수만큼 반복문을 돌려주면서 컴퓨터의 위치 a, b를 입력받습니다. 그래프는 단방향이 아닌 양방향(네트워크)이므로 a 위치에 b를, b 위치에 a를 각각 입력해줍니다.
한번 왔다간 위치인지 체크하는 ch 배열, 지나간 경로를 저장하는 path 배열도 만들어주었어요.
dfs함수를 돌려줍니다. v를 매개변수로 입력받는데, 이것이 컴퓨터와 컴퓨터를 이어주는 역할을 할 겁니다. graph[v] 위치에 있는 변수 nv를 가져오고, 이것이 처음 방문한 것인지(ch[nv] == 0) 확인하고, 처음 왔으면 path에 입력, ch 배열에 방문했음을 기록, dfs[nv]를 통해 더 깊게 파고들어 갑니다.
처음 시작하는 위치가 1번 컴퓨터이므로, 1번 컴퓨터는 방문했음을 기록해주고, dfs(1)을 통해 함수를 시작해줍니다. 그러면 저절로 돌아가면서 탐색을 진행합니다. 그런 다음 path의 길이를 출력해주면 성공입니다.
