[Python Algorithm] 바이러스 BOJ #2606

문제

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

2606번: 바이러스

 

내 문제 풀이

n = int(input())
c = int(input())
network = [[] for _ in range(n)]
queue = []
visited = [False] * n
count = 0

for _ in range(c):
    a, b = map(int, input().split())
    network[a-1].append(b-1)
    network[b-1].append(a-1)

def dfs(x):
    if visited[x]: return
    visited[x] = True

    for i in range(len(network[x])):
        dfs(network[x][i])

dfs(0)
for i in visited:
    if i: count += 1
print(count-1)

👉 DFS 문제로, 2차원 리스트를 생성하여 컴퓨터마다 연결된 컴퓨터들을 표시해서 탐색해주는 것이 포인트

• network라는 비어있는 2차원 리스트를 컴퓨터의 개수 크기로 만들어주었고,
  주어진 네트워크 쌍을 입력받으면서 network 리스트에 연결 표시를 해주었다.
  EX) 2, 5 입력 -> network[1]에 4 append, network[4]에 1 append
• dfs 함수에서 처음에 0을 인자로 받고, network[0] 자리에 저장된 번호의 컴퓨터들은 감염된 것이므로
  for문을 사용하여 network[0]에 저장된 컴퓨터들에 대한 dfs를 진행했다.
  이미 감염된 것을 확인한 컴퓨터는 visited 리스트를 사용하여 중복을 피했다.
• dfs 함수가 종료된 이후에는 visited 함수에 True가 저장된 인덱스의 개수를 결과로 출력했다.

 

💡 피드백

• 일반적인 DFS, BFS 문제와는 조금 다른 스타일이었던 것 같고,
  그래서인지 쉽지만 1시간 정도 시간이 걸렸다.