99클럽 코테 스터디 11일차 TIL + BFS/DFS

백준 25195번 Yes or yes

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	1024 MB	1809	967	708	53.394%

문제

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

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

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

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

조금 쉽게 말하자면

넌 뭘 골라도 날 만나게 될 거야

Twice, YES or YES 가사 중 일부

---

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

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

[입력]

첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$)

이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는 간선이 있음을 의미한다. ($1 \leq u$, $v \leq N$, $u \ne v$)

이후 $M+2$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 개수 $S$ 가 주어진다. ($1 \leq S \leq N$)

이후 $M+3$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호 $s$ 가 차례대로 $S$개 만큼 주어진다. ($1 \le s \le N$)

주어진 그래프는 사이클이 없음이 보장된다. 또한 두 정점을 연결하는 간선은 최대 한 개이다.

팬클럽 곰곰이가 존재하는 정점의 번호는 중복해서 주어지지 않는다.

[출력]

문제에서 설명한 조건에 맞춰서 Yes 또는 yes 를 출력한다.

---

문제 해석하기1

bfs나 dfs로 풀면되는 문제같은데, 곰곰이가 있는 정점을 방문 처리해두고, 곰곰이와 만나게 되면, Yes를 곰곰이를 만나지 않고 이동하게 된다면 yes를 출력할 수 있게 하는 방법을 생각해보았다.

• n,m을 받아준다. input의 값이 그다지 크지 않기 때문에 그냥 input을 사용한다.
• 간선의 정보를 받기 위해 graph를 만들어준다.
  • graph = [[] for _ in range(n+1)]
• 단방향 그래프이기 때문에 해당 그래프에서 u,v를 한번 만 넣어주면 된다.
  • graph[u].append(v)
• 팬클럽 곰곰이가 존재하는 정점의 개수 S를 받고, list을 이용해서 팬클럽 곰곰이 위치한 정점의 번호도 받아준다.
  • list를 가지고 후에 visited를 list만큼 돌면서, 해당 위치를 방문했다는 표시를 해준다.
• bfs 함수를 생성해준다.
  • 일단 bfs이기 때문에 deque를 미리 import 해주어야 한다.
  • queue를 생성하고 시작 정점인 1을 큐에 추가합니다. 이후 방문 표시를 위해 visited[1] = True로 설정한다
  • queue가 빌 때까지 큐의 맨 앞 요소를 꺼내어 탐색을 반복한다.
    • 만약 해당 정점에서 더 이상 연결된 간선이 없다면 'yes'를 반환하여 목적지에 도달할 수 없는 경우를 나타낸다
    • graph[v]의 각 인접 정점 i에 대해 방문하지 않은 정점이면 visited[i] = True로 설정하고 queue에 추가하여 탐색 진행
  • 모든 탐색이 끝나면 'Yes'를 반환
• 마지막으로 팬클럽 곰곰이가 있는 정점 리스트를 돌며 visited 리스트에서 방문 표시를 해줍니다.

from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
s = int(input())
gom = list(map(int, input().split()))
visited = [False for _ in range(n+1)]

def bfs():
    q = deque()
    q.append(1)
    if visited[1]:
        return 'Yes'
    visited[1] = True
    while q:
        v = q.popleft()
        if not graph[v]:
            return 'yes'
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
    return 'Yes'
    
for g in gom:
    visited[g] = True
print(bfs())

⇒ 이렇게 구현했는데 2772ms로 시간이 너무 오래걸려서 다른 방법을 생각해 보았다.

---

문제 해석하기2

bfs가 아니라 갈 수 있는 곳을 깊이 탐색해서 여기서 곰곰 팬클럽이 없으면 다른곳으로 이동하는 것을 생각했어야 했다. 이 방식이 너비우선탐색보다 훨씬 더 빠르게 실행될 수 있을 것이다.
따라서 bfs가 아니라 dfs를 사용하는 방식으로 다시 구현해보았다.

• bfs와 다르게 dfs에서는 스택이나 재귀를 사용해서 구현해준다.
• graph에 간선 정보를 저장하고 팬클럽 곰곰이가 있는 정점을 미리 방문한 것으로 표시한다
• Dfs 함수를 구현해서 재귀적으로 인접 정점을 탐색하도록 한다
  • visited[v]를 True로 설정하여 현재 정점을 방문 처리한다
  • 만약 graph[v]에 연결된 정점이 없다면 yes를 반환하여 탐색 종료를 표시한다
  • 인접한 정점 i에 대해 방문하지 않았다면 dfs(i)를 호출하여 재귀적으로 탐색
  • 한 번이라도 yes가 반환되면 전체 탐색을 중단하고 yes를 반환한다
• 시작 정점인 1에서 DFS 탐색을 시작하고 결과를 출력한다

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
s = int(input())
gom = list(map(int, input().split()))
visited = [False for _ in range(n + 1)]

for g in gom:
    visited[g] = True

def dfs(v):
    if visited[v]:
        return 'Yes'
    visited[v] = True
    if not graph[v]:
        return 'yes'
    for i in graph[v]:
        if not visited[i]:
            result = dfs(i)
            if result == 'yes':
                return 'yes'
    return 'Yes'

print(dfs(1))

⇒ 이렇게 탐색했더니 런타임 에러가 발생했다. DFS를 재귀 방식으로 구현할 때 발생할 수 있는 RecursionError 또는 그래프에서의 무한 루프 등이 주요 원인이라고 생각했다.

⇒ 그래서 재귀를 사용하는 것이 아니라 stack에 쌓고 pop하는 방식을 사용해보았다.

---

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
s = int(input())
gom = list(map(int, input().split()))
visited = [False for _ in range(n + 1)]

for g in gom:
    visited[g] = True

def dfs(v):
    stack = [v]
    while stack:
        node = stack.pop()
        if visited[node]:
            return 'Yes'
        visited[node] = True
        if not graph[node]:
            return 'yes'
        for i in graph[node]:
            if not visited[i]:
                stack.append(i)
    return 'Yes'

print(dfs(1))

⇒ 이 방식으로 바꾸니 그래도 2756ms로 시간이 조금은 줄어든 것을 확인할 수 있었다.
비록 시간은 오래걸리지만 해냈다는 점에서 다행이라는 생각이 들었다.

---

오늘의 회고

문제를 해결하는 과정에서 많은 시행착오가 있었지만, 조금이라도 시간을 줄여서 개발해냈다는 점에 큰 의의를 둔다. 다음부터는 문제를 해결할 때 가장 최적의 알고리즘이 뭔지 더 고민해야겠다는 생각이 들었다.