[백준/2310] 어드벤처 게임 (Python)

Problem : https://www.acmicpc.net/problem/2310

2310번: 어드벤처 게임

 

Difficulty : Gold 4

 

Status : Solved (pypy3)

 

Time : 00:25:12

 

---

 

문제 설명

 

 

어드벤처 게임을 하던 중, 1부터 n까지의 번호가 붙은 방을 지나가야 하는 마법의 미로를 마주쳤다. 각 방 안에는 번호가 붙은 문이 있을 수 있고, 각 문은 해당하는 번호의 방으로 통한다. 방 안에는 레프리콘이나 트롤이 있을 수도 있다.

레프리콘이 있는 방에 들어가면 레프리콘은 모험가의 소지금이 일정 양 이하로 떨어지지 않게 채워준다. 레프리콘은 모험가의 소지금이 일정량 미만일 때에는 그만한 양이 되도록 금화를 채워주고, 소지금이 일정량 이상일 때에는 그대로 둔다. 트롤이 있는 방에 들어가려면 일정량의 통행료를 지불해야 한다. 이는 맨 처음에 모험가가 1번 방에서 시작하려 할 때에도 마찬가지이다.

모험가는 소지금이 0인 상태에서 출발한다. 과연 모험가는 1번 방에서 출발해서 n번 방에 도착할 수 있을까?

 

입력 및 출력

 

입력

 

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타내는 알파벳 하나(E: 빈 방, L: 레프리콘, T: 트롤)와 그 방의 레프리콘이나 트롤이 정해놓은 금액(빈 방일 경우 0이고, 금액은 500보다 작거나 같은 자연수), 그리고 그 방에서 다른 방으로 갈 수 있는 문의 번호들로 이루어진다. 각 줄은 0으로 끝난다. 미로의 방 수가 0개인 입력이 들어오면 입력을 종료한다.

 

출력

 

출력은 각 미로마다 한 줄씩으로 이루어진다. 각 줄에는 1번 방에서 n번 방까지 갈 수 있는지를 "Yes" 또는 "No"로 출력한다.

 

입력 예시

 

3
E 0 2 0
L 10 3 0
T 15 1 2 0
4
E 0 2 3 0
L 201 2 3 0
L 10 4 0
T 15 2 3 1 0
0

 

출력 예시

 

No
Yes

 

 

---

 

풀이

 

레프리콘, 트롤의 경우의 수에 맞추어 탐색할 수 있는 코드를 짜면 된다. 즉 그래프 탐색에 방문 조건이 붙어있는 셈.

 

• 재방문이 가능하다는 점을 생각해보자. 같은 노드에 더 큰 금액으로 방문한다면, 이전에는 통과하지 못했던 노드 역시 통과할 가능성이 생긴다. 즉 단순히 방문 여부를 체크하기보다 금액을 저장하는 것이 좋다.
• (python) 아래 코드는 시간 초과를 일으키는데... pypy3에서만 통과함을 확인하였다. 어떤 부분에서 시간초과를 일으키는걸까..

 

풀이 코드

from collections import deque
import sys

input = sys.stdin.readline
cvt = lambda x : int(x) - 1

while True :
  n = int(input())
  if not n :
    break
  maze_list = list()
  for _ in range(n) :
    typ, money, *next_list = input().split()
    next_list = list(map(cvt, next_list[:-1]))
    maze_list.append([typ, int(money), next_list])

  visited = [-1]*n  
  flg = False

  if maze_list[0][0] == 'T' :
    print('No')
    continue
  elif maze_list[0][0] == 'L' :
    q = deque([(0, maze_list[0][1])])
    visited[0] = maze_list[0][1]
  else :
    q = deque([(0, 0)])
    visited[0] = 0
  
  while q :
    cur, money = q.popleft()
    if cur == n-1 :
      flg = True
      break
    for node in maze_list[cur][2] :
      if maze_list[node][0] == 'T' :
        if maze_list[node][1] > money :
          continue
        next_money = money - maze_list[node][1]
      elif maze_list[node][0] == 'L' :
        next_money = max(money, maze_list[node][1])
      else :
        next_money = money
      if visited[node] < next_money :
        visited[node] = next_money
        q.append((node, next_money))

  print('Yes' if flg else 'No')

풀이 완료!