2606. [Python]바이러스

1. 문제

 

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

2606번: 바이러스

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• DFS(깊이 우선 탐색)

3. 파이썬 코드

 

n = int(input())
m = int(input())
# 컴퓨터 갯수만큼 생성
computers = [[] for _ in range(n+1)]

# 그래프 방식을 통해서 연결된 컴퓨터 리스트 생성
for __ in range(m):
    v1, v2 = map(int,input().split())
    computers[v1].append(v2)
    computers[v2].append(v1)
# 스택에 1번 컴퓨터와 연결된 리스트 생성
stack = list(computers[1])
# 방문 처리 생성
visited = [False] * (n+1)
# 스택값이 비어있을 동안 반복
while stack:
    # stack 의 값을 뽑아 current 에 넣어줌
    cur = stack.pop()
    # current 에 담겨있는 컴퓨터들 탐색
    for j in computers[cur]:
        # 방문처리 안했으면 탐색 후 방문처리 및 스택에 추가
        if visited[j] == False:
            visited[j] = True
            stack.append(j)
# 스택의 값이 0 이면 0 아닐경우 본인 컴퓨터 제외 출력
if visited.count(True) == 0:
    print(0)
else:
    print(visited.count(True)-1)

 

4. 문제를 풀고난 후 생각

 

• 전형적인 DFS 문제로 Graph 방식으로 방향성이 없는 그래프 탐색으로 연결된 컴퓨터들을 탐색을 진행하며 방문 처리를 확인하여 stack에 추가해주는 방식으로 풀었다.
• DFS / BFS 의 경우 틀이 정해져 있어서 별도의 구현은 없고 조건만 생각하여 처리해주면 문제를 풀 수 있다.
• 마지막에 연결이 되지 않았을 경우랑 연결이 되어있는 경우만 나눠서 생각해주면 된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• DFS(깊이 우선 탐색)