[BOJ / 백준] 2606 바이러스 (S3 / DFS) - Python

링크

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

 

 

 

 

문제 해석

컴퓨터 바이러스는 동일한 네트워크에 연결된 다른 PC로 감염된다.
1번 컴퓨터가 바이러스에 감염되었을 때 1번 컴퓨터로 인해서 감염된 컴퓨터의 개수를 구하라.


입력
첫 번째 줄 : n
  n : 컴퓨터의 수
두 번째 줄 : m
  m : 네트워크 상에 연결된 컴퓨터 쌍의 수
나머지 줄 : m개의 쌍 정보


출력
1번 컴퓨터로 인해 감염된 PC 수

 

 

 

 

풀이 & 코드 해석

그래프에서 연결된 노드의 개수를 찾는 문제입니다.

 

인접 리스트를 통해서 구현을 시도하였으며, 새롭게 노드를 방문할 때마다 개수를 count하면서 정답을 구하였습니다.

 

 

 

코드

def dfs(num):
    global ans
    v[num] = True

    for nxt in graph[num]:
        if v[nxt] == True:
            continue
        ans += 1
        dfs(nxt)


n = int(input())
m = int(input())

graph = [[] for _ in range(n + 1)]
v = [False] * (n + 1)

for _ in range(m):
    a, b = list(map(int, input().split()))

    graph[a].append(b)
    graph[b].append(a)

ans = 0
dfs(1)
print(ans)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java