[백준] Python - 바이러스

2606번: 바이러스

 

백준의 그래프 문제 바이러스다.

1번 PC와 네트워크로 연결된 PC들이 주어지고 1번을 제외한 바이러스로 감염시킬 수 있는 PC의 수를 세는 문제이다.

 

DFS나 Union-Find를 사용하면 풀 수 있을 것이라 생각했고 DFS를 사용해서 풀 수 있었다.

 

 

 for i in range(1, c+1): #다음 이동할 컴퓨터
        if G[v][i] and visited[i] == 0: # 네트워크 연결이 되어 있는지, 방문한 적이 있는지
            visited[i] = 1
            infect += 1
            dfs(c, i, visited) # 컴퓨터 수, 기준 PC, 방문

위와 같이 현재 위치를 기준으로 유효한 다음 PC를 찾고 유효한 다음 PC를 기준노드로 삼아 재귀 탐색을 반복한다.

 

 

앞으로는 재귀가 아닌 스택과 반복문을 사용한 DFS를 연습해야겠다.

 

 

 

 

 

GitHub - Floodnut/algorithm: 알고리즘 풀이 모음