[백준] 2606번: 바이러스

문제

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

풀이

stack을 활용한 dfs로 푼 풀이

그래프 탐색을 위해 사용할 수 있는 알고리즘은 dfs와 bfs가 있는데
dfs를 사용했다.

컴퓨터의 수가 100 이하 이기 때문에 시간 복잡도에서 문제가 되지 않는다.

양방향성 그래프이기 때문에 이에 따라 인접행렬에 양쪽 다 연결을 해준다.

이후 만들어진 그래프(graph_pc) 를 사용해서
1부터 연결된 pc 의 수를 센다.

N = int(input())
M = int(input())
graph_pc = [[] for _ in range(N + 1)]

for _ in range(M):
    c1, c2 = map(int, input().split(" "))
    graph_pc[c1].append(c2)
    graph_pc[c2].append(c1)


def dfs(start, N, graph_pc):
    visited = [False] * (N + 1)
    count = 0
    stack = [start]
    visited[start] = True
    while stack:
        cur = stack.pop()
        for next_pc in graph_pc[cur]:
            if not visited[next_pc]:
                stack.append(next_pc)
                count += 1
                visited[next_pc] = True


    return count

print(dfs(1, N, graph_pc))