백준[2606] - 바이러스

 

 

문제

2606번: 바이러스

 

 

 

작성한 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
visited = [0] * (N+1)
order = 1

for _ in range(M):
    u,v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(v):
    global order
    visited[v] = order
    for i in graph[v]:
        if visited[i] == 0:
            order += 1
            dfs(i)

dfs(1)
print(order-1)

- 그래프 → 연결요소 관련 문제라고 생각해서 DFS를 이용하여 문제를 풀었다. (BFS로도 문제를 풀 수 있음)

- N : 컴퓨터 개수 / M : 컴퓨터 끼리 연결된 수 → 각각 입력 받는다.

- 연결된 정보를 저장하기 위해 빈 리스트를 원소로 갖는 graph 라는 리스트를 선언한다. (인덱스를 맞추기 위해 N+1 해준다.)

- 방문 여부를 저장하기 위해 0을 원소로 갖는 visited 라는 리스트를 선언한다. (인덱스를 맞추기 위해 N+1 해준다.)

- 몇 번째 방문했는지를 나타내는 변수 order를 선언한다. (1번 부터 시작이므로 1을 대입했다.)

 

- M번 만큼 for문을 돌리면서 공백을 기준으로 연결 정보를 입력받아 graph에 저장한다.

- 전역변수 order를 사용하여 몇 번째 방문했는지 각 인덱스 별로 visited 리스트에 저장한다.

- for문을 돌면서 graph에 v번 인덱스에 해당하는 원소들을 비교한다.

- 만약 visited 값이 0이라면 → oreder를 +1 해주고, 재귀함수 dfs를 다시 실행한다.

- 최종적으로 시작 컴퓨터인 1번을 뺀 감염된 컴퓨터의 개수를 나타내야 하기 때문에, order-1 의 값을 print()로 출력한다.