[DFS/BFS] 백준 2606 바이러스(DFS 풀이)

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

2606번: 바이러스

 

문제)

 

 

풀이)

def dfs(x):
    global visited
    if visited[x] == False:
        visited[x] = True
        for i in graph[x]:
            dfs(i)
    else:
        return 0

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
li = int(input())

for i in range(li):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

count = 0
dfs(1)
for i in range(2, len(visited)):#1번은 제외
    if visited[i] == True:
        count += 1
print(count)

 

이 문제는 dfs로 해결했는데, 간단한 문제이다. 물론 bfs로도 충분히 가능할 것이다.

 

무조건 1번에서 시작하므로 1번 노드에서 각 노드를 방문 표시한 개수를 센다면 문제를 해결할 수 있을 것이라고 생각했다.

따라서 입력으로 그래프를 생성하고(이때 그래프는 i번 노드에 연결된 노드를 모두 저장한다.),

DFS를 이용하여 1번에서 연결된 노드를 방문 표시해준다.

 

마지막으로 방문 표시한 개수를 세는데, 본인 노드(1번 노드)는 카운트하지 않으므로 2번 노드부터 끝까지 방문 표시된 노드 개수를 센다.