백준 2606 - 바이러스

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

해당 문제는 그래프로도 풀어봤고, 새로운 풀이인 DFS로 풀이를 진행하였다.

N = 컴퓨터의 수, M은 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수

그 이후부턴, 한줄에 한쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

해당 문제에서 DFS를 적용한 이유는 다음과 같다.

"단순히 그래프로도 풀이를 할수 있지만, DFS 알고리즘을 사용하면 시간복잡도가 O(2M)이 된다.'

먼저 N, M을 입력받고, adj 배열에 각각 컴퓨터를 연결시킨다.

N = int(input())
M = int(input())

adj = [[] for i in range(N)]

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

연결의 편의성을 위해서 0부터 시작하는것이 아닌 1부터 시작하도록 각각 인접 배열에 - 1씩을 해줘서 숫자를 맞춘다.

DFS를 위해서 컴퓨터의 갯수만큼 방문을 했는지 안했는지 확인하기 위한 visit 배열을 선언하고, 초기에는 방문하지 않았으므로, False로 채운다.

visit = [False] * N

 

그 이후 실질적으로 문제를 풀기 위한 기본적인 DFS 알고리즘을 구현한다. 

해당 알고리즘의 설명은 다음과 같다.

def dfs(u) :
    visit[u] = True

    for v in adj[u] :
        if not visit[v] :
            dfs(v)

DFS는 먼저 들어온 인자를 바탕으로 방문을 했는지 체크를 한다. 그 이후, 해당 인접배열에 연결된 친구들을 순회하면서, 방문을 하지 않았을 경우에만 다시 DFS 제귀를 진행하는 식으로 하면, 연결된 친구들만 Visit이 True로 변경되게 된다.

초기에 시작위치가 1번으로 주어졌기 때문에 DFS(0)를 통해서 1번부터 시작한다.

dfs(0)

count = 0

for i in range(1, N) :
    if visit[i] :
        count += 1

print(count)

 

결국 1번 컴퓨터에 웜 바이러스가 걸렸을경우, 방문을 한 간선의 갯수만 세면 1번을 통해서 전파된 바이러스의 총 합을 구할수 있다.

 

# 백준 2606 - 바이러스
# 분류 : DFS

N = int(input())
M = int(input())

adj = [[] for i in range(N)]

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

visit = [False] * N

# dfs
def dfs(u) :
    visit[u] = True

    for v in adj[u] :
        if not visit[v] :
            dfs(v)

dfs(0)

count = 0

for i in range(1, N) :
    if visit[i] :
        count += 1

print(count)