[백준/Python] 2606번: 바이러스 (재귀 DFS 사용)

1. 문제 

2606번: 바이러스

 

2. 코드 

n = int(input())
# 노드 개수 
size = int(input())
# n번 노드에 연결된 노드 
graph = [[] for _ in range(n+1)]
# 방문한 노드는 1, 방문하지 않은 노드는 0
visited =[0]*(n+1)
for i in range(size):
    a,b = map(int,input().split())
    # 그래프 넣어주기 ~ 
    graph[a]+=[b]
    graph[b]+=[a]


def dfs(v):
    # 방문한 노드는 1로 만들어주기 
    visited[v]=1
    for nx in graph[v]:
        #만약 방문하지 않았다면 , 0
        if visited[nx] == 0:
            # 재귀함수로 다시 dfs ㄱㄱ 
            dfs(nx)

# dfs 
dfs(1)

# 1번 노드는 빼주기 
print(sum(visited)-1)

 

3. 해설 

다른 DFS,BFS문제보다 쉬운 문제였다. 

1. 처음에는 그래프를 만들 때 append를 사용했는데 ,, +[노드]가 훨씬 좋을 것 같다. 

2. 그래프 탐색에서 'visited' 배열을 만드는 게 중요하다 .. 

     visited[v]에서 v는 노드의 번호이다. 

3. visited[v]의 번호를 체크하여 0이라면 방문하지 않은 노드, 1이라면 방문했던 노드 

4. 문제에서는 1과 연결된 노드의 수를 구하는 것이 목표이다. 그러니 이 visited된 노드만 세면 되는 것 !