[백준] 2606번: 바이러스 - 파이썬

😀 서론

DFS를 제대로 다뤄보지 못하여 오늘부터 DFS, BFS 문제 하나씩은 풀 예정이다!
그래서 도전해본 문제는 "바이러스" 전에 스터디때 도전하였다가 실패한 문제이다. 그때는 DFS와 BFS의 개념을 잘 몰랐기에 실패하였으나, 이제는 다르다!ㅎㅎ

 

📕 풀이

주어진 컴퓨터의 수로 리스트 컴프리헨션으로 그래프를 만들고 그 후에 주어지는 인풋 값을 각자 위치에 넣어준 뒤 DFS를 돌렸다.

 

💻 코드

import sys
input = sys.stdin.readline

# dfs 정의
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
com = int(input().rstrip()) # 컴퓨터의 갯수
visited = [False] * (com+1) # 방문을 체크하기 위한 불리안 리스트
connect = [] # 1 : 1 연결로 주어질 인풋을 담을 리스트
graph = [[] for i in range(com+1)] # 최종적인 그래프

for i in range(int(input().rstrip())):
    connect.append(list(map(int, input().rstrip().split()))) # 연결된 컴퓨터 담음

for j in connect: # 연결된걸 하나하나 뜯어봄
    for k in range(1, com+1): 
        # 어떤 컴퓨터가 연결되었는지 체크
        if k in j:
            graph[k].append(*set(j)-{k}) # 그래프에 값 집어넣음

# 예제 입력 넣으면, 아래와 같이 그래프 생성
# graph = [
#     [],
#     [2,5],
#     [1,3],
#     [2],
#     [7],
#     [1,2,6],
#     [5],
#     [7]
# ]

dfs(graph, 1, visited)
# 방문한 적이 있다면, 감염됐다는 것! 즉 True 값을 카운트해서 출력한다. -1 한 이유는 1번 컴퓨터를 통해 
# 감염되는 컴퓨터의 수를 출력하는 것이니 1번 컴퓨터는 제와한다.
print(visited.count(True)-1)

윔바이러스 무셔!

📎 문제 링크 : 바이러스

2606번: 바이러스