[TIL 2024.07.18]Python DFS 활용

오늘 진행한 일들

• 알고리즘 강의 시청
• 알고리즘 코드 문제 풀이

알고리즘 문제

오늘도 백준에서 제공하는 알고리즘 문제를 푸는데에 집중했다. 문제는 여러 테스트 케이스를 처리하면서, 각 테스트 케이스마다 주어진 노드와 간선을 기반으로 그래프를 인접 리스트 형태로 생성하고, DFS(깊이 우선 탐색)를 사용해 각 그래프를 탐색하는 것이었다.

상근이의 여행

• 여행할 국가의 수는 N이고 각 국가를 잇는 비행 스케줄이 주어진다.
• 모든 국가를 여행할 수 있도록 최소한의 비행기 종류를 사용해야 한다.
• 다른 국가를 거쳐서 이동할 수 있고 이미 방문한 국가를 다시 방문할 수 있다.
• 결과적으로, 최소한의 비행기 종류 개수를 계산하여 출력한다.

작성한 코드

defaultdict(list)

given_list = defaultdict(list)

defaultdict(list)는 기본값이 빈 리스트인 딕셔너리를 생성한다. 키가 존재하지 않을 때 자동으로 빈 리스트를 할당한다.

given_list[a].append(b) 및 given_list[b].append(a)

for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        given_list[a].append(b)
        given_list[b].append(a)

노드 a의 인접 리스트에 노드 b를 추가하고, 노드 b의 인접 리스트에 노드 a를 추가한다. 이를 통해 양방향 간선을 설정한다.

visited_country = defaultdict(bool)

visited_country = defaultdict(bool)

defaultdict(bool)은 기본값이 False인 딕셔너리를 생성하여 노드 방문 여부를 추적한다. 노드를 방문하면 True로 설정한다.

dfs_stack.append(country)

for country in next_countries:
            if not visited_country[country] and country not in dfs_stack:
                dfs_stack.append(country)

DFS(깊이 우선 탐색)를 수행할 때 스택에 다음 방문할 노드를 추가한다. 스택에서 노드를 꺼내어 탐색을 계속한다.

전체 코드

import sys
from collections import defaultdict

T = int(sys.stdin.readline())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())

    given_list = defaultdict(list)

    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        given_list[a].append(b)
        given_list[b].append(a)

    visited_country = defaultdict(bool)

    dfs_stack = [1]
    travel_count = 0

    while dfs_stack:
        top = dfs_stack.pop()
        visited_country[top] = True
        next_countries = given_list[top]

        for country in next_countries:
            if not visited_country[country] and country not in dfs_stack:
                dfs_stack.append(country)
                travel_count += 1
    print(travel_count)