99클럽 코테 스터디 11일차 TIL / DFS(깊이 우선 탐색)

✏️ 문제

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

 

 

N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.

투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.

투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.

오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 "YES or YES" 에서 다음과 같은 가사를 듣게 된다.

조금 쉽게 말하자면 넌 뭘 골라도 날 만나게 될 거야 Twice, YES or YES 가사 중 일부

 

투어리스트 곰곰이는 Twice의 노래 가사처럼, 뭘 골라도 팬클럽 곰곰이를 만나게 될 것인지 궁금해졌다.

투어리스트 곰곰이가 어떻게 이동하더라도 팬클럽 곰곰이를 만나게 된다면 "Yes" 를, 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes" 를 출력하자.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 G4

✅ 소요 시간: 1시간 5분

✅ 권장 시간: 1시간 15분

 

계속 고민하다가 다른 분 코드 클론 코딩하면서 제출한 거라 혼자 힘으로 푼 건 아님

 

👩‍🏫 참고

https://subinze.tistory.com/m/400

[백준/Python] 25195번(DFS)_Yes or yes

 

💡 풀이

1) 문제 유형 파악

최소 횟수, 최단 거리를 생각할 필요 없이 1번 노드~리프 노드까지의 경로를 하나씩 다 확인하면서 팬클럽 곰곰이의 등장 여부를 체크하는 게 중요하겠구나 라는 생각이 들어 DFS를 떠올렸다.

 

2) 구현

오늘 문제는 코드에 바로 주석을 달아서 설명을 대신하려고 한다. 어떻게 풀어야 할지 감을 아예 못 잡은 정도는 아니었는데 구현을 못해서 자력으로 못 풀었다는 게 너무 아쉽다.

 

import sys

# 재귀 깊이 더 깊게 설정
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

N, M = map(int, input().split())

# 단방향 그래프 생성
graph = {k: [] for k in range(1, N+1)}

for _ in range(M):
    u, v = map(int, input().split())
    
    graph[u].append(v)

S = int(input())

fanclub = list(map(int, input().split()))

# 방문 처리용 배열
visited = [False]*(N+1)

def DFS(start_node):
    global flag # 팬클럽 곰곰이를 만났는지 체크하기 위한 변수(기본 값은 False)

    '''
    [종료 조건 1] 
    현재 확인 중인 노드가 팬클럽 곰곰이 노드 리스트에 속할 경우 종료
    '''
    if start_node in fanclub:
        return
    
    visited[start_node] = True
    
    '''
    [종료 조건 2]
    이전에 종료되지 않았고 현재 확인 중인 노드가 리프 노드일 경우 팬클럽 곰곰이를 마주치지 않는 경로로 왔다는 뜻이기 때문에 flag = True로 바꾼 후 종료
    '''
    if graph[start_node] == []:
        flag = True
        return
    
    # 이전에 종료되지 않았다면 현재 확인 중인 노드(start_node)와 연결된 노드(node) 탐색
    for node in graph[start_node]:
        # node가 리프 노드가 아니면서 아직 방문하지 않은 곳일 때 DFS 수행
        if graph[node] != [] and not visited[node]:
            DFS(node)
        # node가 리프 노드이면서 팬클럽 곰곰이 노드 리스트에 속하지 않을 flag = True로 바꾼 후 종료
        elif graph[node] == [] and node not in fanclub:
            flag = True
            return

flag = False

DFS(1)

# DFS를 다 돌았을 때 flag = True면 팬클럽 곰곰이를 만나지 않는 경로가 있다는 뜻
if flag:
    print("yes")
else:
    print("Yes")

 

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 일찍 종료하기 위해 현재 확인 중인 노드와 연결된 노드가 리프 노드인지 아닌지 확인하는 방법을 떠올리는 게 어려웠다. 코드를 한 줄씩 읽다 보니까 아~ 하게 됐던 부분이다.

❗ 배운 점

• 빈 return도 쓰일 때가 있다.
• 코드 참고했던 분 블로그를 다시 보다 보니 DFS에서의 return 의미에 대해 좀 더 찾아봐야겠다는 생각이 든다.