[백준] 2606번 : 바이러스

문제

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

풀이

[백준] 2606 : 바이러스 🥈(실버3)
🎯 45.766%
⏰ 걸린 시간 :20분

• 알고리즘 유형 : [BFS & DFS]

✅ 문제 요약

0. 첫째 줄에는 컴퓨터의 수가 주어진다.
1. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
2. 컴퓨터간 연결되어 있는 컴퓨터 들이 주어진다.
3. 연결되어 있는 컴퓨터중 1번이 감염되면 나머지도 다 감염된다.
   

✅ 출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

✅ 풀이방법 & recursion DFS 알고리즘로 푼 이유?

✔️ 재귀 함수를 돌면서 연결된 요소들을 하나로 보고 깊이 탐색이 유리
0. DFS 알고리즘 특성 깊이 탐색을 한다.
1. 해당 문제의 DFS는 바이러스 컴퓨터를 체크하는 것이다.
2. 깊게 탐색후 바이러스 감염을 다 체크하고 나오는 것이 목표이기 때문에 DFS가 적합하다고 판단했다.

코드(code)

import sys
input = sys.stdin.readline
# N : 컴퓨터 대수, M:직접 연결되어 있는 컴퓨터 쌍의 수
N = int(input())
M = int(input())
graph = [[0]*(N+1)for i in range(N+1)]
visited,needvisit = [], []

for i in range(M):
    a, b = map(int,sys.stdin.readline().split())
    graph[a][b] = 1
    graph[b][a] = 1

# recursion DFS
def DFS(n):
    visited.append(n)
    next = 0

    for i in range(N+1):
        if graph[n][i] == 1 and i not in visited and i not in needvisit:
            needvisit.append(i)
    if needvisit:
        next = needvisit.pop()
        DFS(next)
    if not needvisit: # 재귀 끝내는 조건 
        return False
DFS(1)
print(len(visited)-1)

회고

recursion DFS는 이제 너무 익숙하다.
✔️유형 : 각 노드가 연결되어 있는것들 찾는유형 , 특정 구역 개수 찾는 유형

조금 부족하다고 느끼는 BFS문제를 풀면서 더 익숙해져 보자

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/BFS_DFS/2606(%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4).py