[파이썬]백준 2606 바이러스

링크

백준 2606 바이러스

학교에서, 싸피에서 벌써 두번째 듣는 dfs임에도 처음에 제대로 안익혀 놔서 그런지 영 새롭다.
앞으로 dfs, bfs 문제들을 집중적으로 풀어볼 생각이다.
해당 문제는 단순히 dfs만 구현하면 되는 단순한 문제였음에도 꽤나 시간이 걸렸다.
머리로 이해하는 것은 어렵지 않으나 항상 손이 익숙해지는데 시간이 좀 걸린다.
포기하지 않고 계속 쳐야한다. 쳐야 익숙해지고 그래야 100% 이해가 된다.

정답 코드 (재귀)

def dfs(v, g):
    visited[v] = 1
    for u in g[v]:
        if visited[u] != 1:
            dfs(u, g)

n = int(input()) #노드의 갯수
e = int(input()) #간선의 갯수
g = [[] for _ in range(n + 1)] #연결리스트
visited = [0] * (n + 1)

for _ in range(e):
    v, w = map(int, input().split())
    g[v].append(w)
    g[w].append(v)

dfs(1, g)
print(visited.count(1) - 1)

정답 코드 (스택)

def dfsStack(v, g):
    stack = [v]
    while stack:
        cur = stack.pop()
        for node in g[cur]:
            if visited[node] == 0:
                stack.append(node)
        visited[cur] = 1

n = int(input()) #노드의 갯수
e = int(input()) #간선의 갯수
g = [[] for _ in range(n + 1)] #연결리스트
visited = [0] * (n + 1)

for _ in range(e):
    v, w = map(int, input().split())
    g[v].append(w)
    g[w].append(v)


dfsStack(1, g)
print(visited.count(1) - 1)

알게된 것👨‍💻

• 재귀든 스택이든 핵심아이디어는 내가 있는 노드를 방문했다고 표시하고 갈수 있는 노드가 없을 때까지 인접 노드로 이동하는 것이다.