[백준] 어드벤처 게임

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

 

백준 2310번: 어드벤처 게임

파이썬

문제를 풀었던 방법

DFS를 사용해서 풀었습니다.

 

방문처리에 대해서

들렀던 곳을 또 들려야 최소가 되는 경우를 고려했었기 때문에 처음에는 방문처리를 하지 않았습니다..

 

사진과 같은 경우에 빈방에서의 소지금이 0원이라면 그냥 일반적인 방문처리로는 트롤방으로 바로 가는 경우가 없습니다.

하지만 방문처리를 하지 않는다면 빈방(소지금:0) → 레프(소지금:20) → 빈방(소지금:20) → 트롤방(소지금:10) 이런식으로 갈 수 있어서 이걸 고려했습니다.

 

하지만 아예 방문처리를 안하니까 당연히 시간초과가 났고,

 

이걸 해결하기 위해 방문처리를 할때 방문 처리 배열에 현재 가지고 있는 소지금을 저장했습니다.

→그래서 다시 들릴때 현재 소지금 > 이전 들릴때 소지금이면 방문할 수 있도록 처리를 했습니다.

 

제출 코드

# 어드벤처 게임

def dfs(rooms, n):
    stack = [[1, 0]] # 시작 room number, 가지고 있는 돈
    
    # 같은 돈을 소지하고 다시 같은 방에 가는건 막자
    visited = [None] * n
    visited[0] = 0
    
    while stack:
        [now_room_number, now_money] = stack.pop()

        if now_room_number == n:
            return 'Yes'

        for next_room_number in rooms[now_room_number - 1][2]:
            next_idx = next_room_number - 1
            room_type = rooms[next_idx][0]
            room_value = rooms[next_idx][1]

            # 룸 타입 확인
            if room_type == 'E':
                next_money = now_money
            elif room_type == 'L':
                next_money = max(now_money, room_value)
            else:
                if now_money >= room_value:
                    next_money = now_money - room_value
                else:
                    continue

            # 들리지 않았거나, 현재 소지금이 아까보다 많을때만 갈 수 있게
            if visited[next_idx] == None or visited[next_idx] < next_money:
                visited[next_idx] = next_money
                stack.append([next_room_number, next_money])

    
    return 'No'


while True:
    # n = 0이 되면 종료
    n = int(input())
    if n == 0:
        break

    rooms = []
    for _ in range(n):
        input_arr = input().split(' ')
        # rooms에 저장되는 형식 [방 타입(빈방, 레프리콘, 트롤), 돈, 다음 방 정보(list)]
        rooms.append([input_arr[0], int(input_arr[1]), list(map(int, input_arr[2:len(input_arr) - 1]))])

    print(dfs(rooms, n))

 

 

근데... 다른 제출한 사람들의 실행 시간이 꽤나 차이가 나서 보니까

방문처리를 그냥 (들림 / 안들림)으로만 해도 충분히 맞는 것 같음...

그래서인가 무수한 데이터 추가 요청