[TIL] 99클럽 코테 스터디 11일차 TIL - DFS : 백준 25195 Yes or Yes 풀이 with python

Today's keyword : DFS

 

문제설명

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

 

방향 그래프에서 1번 정점에서 시작하여 팬클럽 곰곰이를 만날 수 있는지를 확인하는 문제입니다. 팬클럽 곰곰이가 있는 정점이 여러 개 주어지며, 1번 정점에서 시작하여 도달할 수 있는 정점 중 팬클럽 곰곰이가 있는 정점이 포함되어 있는지를 판단해야 합니다.

문제풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100001)

def dfs(now_v):
    # 현재 정점이 팬클럽 곰곰이가 있는 정점이거나 이미 방문한 정점이라면 종료
    if visited[now_v] or now_v in is_bear:
        return False

    visited[now_v] = True

    # 현재 정점이 더 이상 갈 수 없는 정점이라면 "yes" 출력
    if not graph[now_v]:
        print("yes")
        exit(0)

    # 다음 정점으로 이동하여 DFS 수행
    for next_v in graph[now_v]:
        if next_v not in is_bear and not visited[next_v]:
            if dfs(next_v):  # 다음 정점에서 "yes"가 출력되면 종료
                return True

    visited[now_v] = False  # 백트래킹
    return False

if __name__ == "__main__":
    N, M = map(int, input().split())

    graph = [[] for _ in range(N + 1)]
    visited = [False] * (N + 1)
    
    # 그래프 구성
    for _ in range(M):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)

    S = int(input())
    is_bear = set(map(int, input().split()))  # 팬클럽 곰곰이가 있는 정점 집합

    # DFS 시작
    dfs(1)
    print("Yes")  # 모든 경로에서 팬클럽 곰곰이를 만날 수 있는 경우

 

1. 그래프 구성:

- graph 리스트를 사용하여 인접 리스트 형태로 그래프를 구성합니다. 각 정점에서 연결된 정점들을 저장합니다.

2. 팬클럽 곰곰이가 있는 정점 집합

- is_bear를 집합으로 사용하여 탐색 시 더 빠르게 확인할 수 있도록 했습니다.

3. DFS 탐색

- dfs 함수를 통해 1번 정점에서 시작하여 도달할 수 있는 모든 정점을 탐색합니다.
- 현재 정점이 팬클럽 곰곰이가 있는 정점이거나 이미 방문한 정점이라면 탐색을 종료합니다.
- 현재 정점이 더 이상 갈 수 없는 정점이라면 "yes"를 출력하고 종료합니다.
- 다음 정점으로 이동하여 DFS를 계속 수행합니다.

4. 출력: DFS가 끝난 후, 팬클럽 곰곰이를 만날 수 있는 경로가 없었다면 "Yes"를 출력합니다.

 

 

오늘의 회고 

 

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL