[백준] 2606번 - 바이러스 (BFS, DFS) - 결과 포함

www.acmicpc.net/problem/2606

2606번: 바이러스

네트워크 상에 컴퓨터들이 연결되어 있을 때 바이러스가 걸리는 컴퓨터의 갯수를 출력하는 것으로

네트워크라는 단어를 들었을 때 바로 그래프가 생각난다.

 

문제가 BFS, DFS를 사용하는 것에 초점을 맞추었다는 생각이 든다.

 

정점과 간선 정보를 알고 있고 문제에서 무조건 1번 컴퓨터가 바이러스에 감염되었다고 조건을 달았기 때문에

입력 받은 그래프에서 1번 정점부터 DFS나 BFS로 순회하면서 탐색한 정점의 갯수를 세는 방법을 생각했다.

 

난 DFS를 이용해서 풀었다.

[소스코드]

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

graph = [[] for i in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

visited = [False] * n
result = 0

def dfs(v, result):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            result = dfs(i, result + 1)
    return result

print(dfs(0, 0))

먼저 정점과 간선의 정보를 입력받아 그래프를 생성한다.

정점의 수에 맞게 visited 리스트를 만들어 놓는다.

DFS 함수를 구현할 때 정점의 갯수를 셀 수 있는 변수를 넘겨준다.

DFS에서 다음 DFS로 갈 때, 즉 방문하지 않은 정점이 존재해서 해당 정점으로 이동할 때

1을 더한 값을 전달함으로써 방문한 정점의 카운트를 센다.

 

결과적으로 마지막에는 탐색했던 모든 정점의 수가 result로 리턴되면서 답을 출력한다.

 

재귀함수를 사용해본지 오래되서 처음에 재귀함수로 더한 값을 전달하는 것을 생각하는데 시간이 좀 걸렸다.