백준 2606번 파이썬 풀이

DFS 알고리즘의 활용에 익숙해지기 위해 해당 유형의 문제를 몇문제 더 선정해서 풀어볼까 한다.

이번 문제는 첫 시도만에 정답을 제출했다.

#백준 2606번

total_num = int(input())
connected_num = int(input())

def find_infected(v:int, neighbor:dict, visited:dict) -> int:
    if visited[v]:
        return 0
    else:
        visited[v] = True
        count = 1
        for adjacent in neighbor[v]:
            count += find_infected(adjacent, neighbor, visited)
        return count

if total_num <= 1:
    print(0)
else:
    neighbor = {}
    visited = {}
    for num in range(1, total_num + 1):
        neighbor[num] = []
        visited[num] = False
    
    for _ in range(connected_num):
        a, b = map(int, input().split())
        neighbor[a].append(b)
        neighbor[b].append(a)
    
    print(find_infected(1, neighbor, visited) - 1)