1. 오늘의 문제
오늘은 문제가 뭔가 비문학 같은 느낌이었다.
출제자가 트와이스 팬인게 틀림없다.
어쨋든 오늘의 문제는 다시한번 노드탐색. 하지만 트와이스를 곁들인.
곰곰이를 어디로 가든 만날 경우에는 Yes, 만나지 않고 경로가 끝난다면 yes를 출력한다.
문제
N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.
투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.
투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.
오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 "YES or YES" 에서 다음과 같은 가사를 듣게 된다.
| 조금 쉽게 말하자면 넌 뭘 골라도 날 만나게 될 거야 Twice, YES or YES 가사 중 일부 |
투어리스트 곰곰이는 Twice의 노래 가사처럼, 뭘 골라도 팬클럽 곰곰이를 만나게 될 것인지 궁금해졌다.
투어리스트 곰곰이가 어떻게 이동하더라도 팬클럽 곰곰이를 만나게 된다면 "Yes" 를, 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes" 를 출력하자.
2. 원리
오늘 문제는 비교적 간단한게 순환되는 노드가 없다.
따라서 visited같이 방문 체크를 할 필요가 없이 순서에 따라 노드를 내려가기만 하면 된다.
그리고 팬클럽 곰곰이가 있는 노드는 더 이상 탐색할 필요가 없다.
팬클럼 곰곰이의 위치를 표시하고, 다른 노드를 따라 내려가면서 더 이상 내려갈 노드가 없는 노드를 찾으면 그 부분이 여행이 끝나는 지점이다.
3. 코드
from collections import deque
from sys import stdin
put = stdin.readline
nodes, lines = map(int, put().split())
# 곰곰이를 만나면 해당 노드와 연결된 모든 노드를 제외한다.
route = [[] for node in range(nodes + 1)]
for line in range(lines):
pNode, direction =map(int, put().split())
route[pNode].append(direction)
gomsNum = int(put())
gomsLst = list(map(int, put().split()))
for goms in gomsLst:
route[goms] = "곰곰"
que = deque()
que.append(1)
find = False
while que:
position = que.popleft()
if route[position] == "곰곰":
continue
if route[position] == []:
find = True
for nextPosition in route[position]:
que.append(nextPosition)
if find:
print("yes")
else:
print("Yes")
4. 느낀점
오늘 문제는 다소 쉬웠다.
복잡한 계산이나 노드 순서를 정할 필요 없이, 타고 내려가기만 하는 문제라서 그런 것 같다.
그래도 중간에 곰곰이를 만나면 어떻게 처리해야할지를 조금 고민했다.
무언게 문제를 풀어나가는 시간이 재밌고 즐겁다.
