[백준 알고리즘] 2606. 바이러스 - DFS(깊이우선탐색)

2606. 바이러스

 

 

 

 

 

 

DFS 처음 배우고나서 제대로 푼 첫문제인데, 토할 뻔 했다...

 

문제 자체는 어렵지 않았으나, 백트래킹 배우다가 DFS문제 다시 풀려니 기억이 잘 나지 않아 꽤나 헤맸다....

 

이제는 다시 안 헤매겠지...? ㅎㅎ

 

 

 

 

빨리 DFS 문제가 익숙해지는 날이 오길....

 

 

 

 

 

def DFS(v):
    visited[v] = 1
    stack.append(v)
    while stack:
        for w in Graph[v]:
            if visited[w] == 0:
                visited[w] = 1
                stack.append(v)
                v = w
                break
        else:
            v = stack.pop()
    return sum(visited)-1




V = int(input())
E = int(input())
Graph = [[] for i in range(V+1)]

for _ in range(E):
    s, e = map(int, input().split())
    Graph[s].append(e)
    Graph[e].append(s)
visited = [0] * (V + 1)
stack = []
print(DFS(1))

 

 

www.acmicpc.net/problem/2606

2606번: 바이러스