[Python] 백준 2606번 - 바이러스

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

2606번: 바이러스

학기 중 알고리즘 수업 들을 때 그래프 과제에서 절망했던 경험이 있다.. ㅎ

그래프는 조금하면 익숙해진다고 하는데 난 아직 아니라서 천천히 많이 풀어보려고 한다.

이번 문제는 어렵진 않았는데 count 세는 부분을 dfs 함수 내부에 넣지 않는 게 중요한 것 같다.

dfs 함수 내부에 넣었더니 지 멋대로 먼저 print돼서 애 좀 먹었다 :(

 

import sys
def dfs(v):
    visited[v] = 1
    for i in range(len(adjList[v])):
        w = adjList[v][i]
        if not visited[w-1]:
            dfs(w-1)

n = int(sys.stdin.readline()) #컴퓨터의 수 (노드)
m = int(sys.stdin.readline()) #직접 연결되어 있는 컴퓨터 쌍의 수 (에지)
adjList = [[] for i in range(n)]
visited = [0 for i in range(n)] #0: False, 1: True

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adjList[a-1].append(b)
    adjList[b-1].append(a)

dfs(0)
count = 0
for i in range(1, n):
    if visited[i] == True:
        count += 1
print(count)

 

 

 

 

---

 

 

#220121

다시 풀어봤다.

위에서 보니 바이러스 걸린 컴퓨터 수를 dfs 함수 내부에 넣지 않는 게 중요한 것 같다고 했는데 이번 코드에서는 안에서 계산했다(?)

확실히 이 코드가 훨씬 간결한 듯... 왠지 뿌듯

import sys
input = sys.stdin.readline

def dfs(x):
    global virus
    visited[x] = 1
    for i in adj[x]:
        if not visited[i]:
            virus += 1
            dfs(i)

n = int(input()) #컴퓨터 수
m = int(input()) #네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
visited = [0 for _ in range(n+1)]
adj = [[] for _ in range(n+1)]
virus = 0
for _ in range(m):
    com1, com2 = map(int, input().split())
    adj[com1].append(com2)
    adj[com2].append(com1)

dfs(1)
print(virus)