[Python/파이썬] [🥈3] 백준 알고리즘 2606 - 바이러스

📖[Python/파이썬][🥈3] 백준 알고리즘 2606 - 바이러스

📜문제

---

DFS(깊이우선탐색)

• 임의의 한 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 자기 자신을 호출하는 재귀/순환 알고리즘의 형태임
• 노드 방문 여부를 검사해놔야 무한루프에 빠질 위험이 줄어듦
• 주로 백트래킹과 함께 쓰여, 모든 노드를 다 방문하는 것을 차단함

---

📕풀이방향

내 포스팅 : [Python/파이썬] [🥈2] 백준 알고리즘 11724 - 연결 요소의 개수

이전에 포스팅한 "연결 요소의 개수"문제의 DFS개념과 풀이방법이 매우 흡사하다!
똑같이 입력값 저장, 노드를 MAP 형태로 저장하고, visited라는 빈 list를 만들어,
dfs(i) 함수로 방문검사를 하면서 첫 방문시 visited[i]=1 체크해주면 된다.
다만, 이전포스팅과 달라진 점은 1번 컴퓨터가 웜바이러스에 걸렸을 때만 검사하면 된다.
그리고 sum(visited)-1을 출력해주면 끝! (1컴퓨터 자신은 빼야하니까)

👉🏻 ex) n=7일 때 1-2-3-4만 연결되어 있으면, 5-6-7은 웜바이러스 걸렸든 말든 검사할 필요가 없음!

---

📝알고리즘 구현순서

1. n,m과 node를 입력받으면서 amap에 map형태로 저장하자
2. visited list를 0으로 초기화하고 dfs()함수를 만들고, for loof로 amap[1]의 요소(i)만
   dfs(i)를 호출하자
   👉🏻 1번에 연결되어있는 컴퓨터들만 확인하면, 나머지 컴퓨터는 웜바이러스 걸리든말든 상관X
   (for loof로 i를 1~n까지 다 돌 필요가 없음)

---

💻결과코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())
m = int(input().rstrip())
node = [list(map(int, input().split())) for _ in range(m)]
amap = [[] for _ in range(n+1)]
visited = [0]*(n+1)

for u,v in node:
    amap[u].append(v)
    amap[v].append(u)

def dfs(v):
    visited[v] = 1
    for i in amap[v]:
        if not visited[i]:
            dfs(i)

for i in amap[1]:
    if not visited[i]:
        dfs(i)

print(sum(visited)-1)   #1번컴퓨터 자신 카운팅은 빼주기

---

✏️1. n, m, node 입력받으면서 amap 저장

import sys
input = sys.stdin.readline

n = int(input().rstrip())
m = int(input().rstrip())
node = [list(map(int, input().split())) for _ in range(m)]
amap = [[] for _ in range(n+1)]

#Graph 형식으로 저장
for u,v in node:
    amap[u].append(v)
    amap[v].append(u)

---

✏️2. dfs()함수 구현과 for loof에서 호출

visited = [0]*(n+1)


def dfs(v):
    visited[v] = 1      #방문안한 노드마다 방문기록 0 → 1 
    for i in amap[v]:   #해당 노드와 연결된 노드들 방문검사
        if not visited[i]:
            dfs(i)

for i in amap[1]:       #amap[1] 요소만 검사하면 됨
    if not visited[i]:
        dfs(i)

print(sum(visited)-1)   #1번컴퓨터 카운팅 빼기

❓"for i in amap[1]"만 검사하는 이유

알고리즘 구현순서 1번에서 amap으로 [1]번 컴퓨터와 연결된 노드를 amap[1]에 저장해뒀기 때문!

amap[1] = 2, 5
amap[2] = 1, 3, 5
...
...
amap[7] = 4

이렇게 인덱싱 해뒀기 때문에 amap[1]은 1번컴퓨터의 연결노드만 검사함

---

📚정리

내 포스팅 : [Python/파이썬] [🥈2] 백준 알고리즘 11724 - 연결 요소의 개수

이전 포스팅에서 다뤄봤던 유형의 DFS 개념이라 풀이하기 수월했다.
이전 포스팅에서도 언급한대로, DFS 라고해서 dfs()함수 안에서 무조건 해결하려고 하지말고,

• DFS를 어떤시점에서 호출할지,
• 호출했을 때는 또 어떤부분에서 return, 즉 종료할지

를 생각하면서 알고리즘을 설계하자!