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