[백준] 2310번 : 어드벤처 게임 Python

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

2310번: 어드벤처 게임

 

문제 유형으로는 dfs, bfs문제라고 나와있는데 나는 백트래킹 문제라고 생각한다. 

bfs로 먼저 접근을 했었는데, 방문처리가 중복이 되는 경우가 발생하는 문제점이 있었다. 

또한 문제에서 제시한 조건으로 트롤을 만났을때 통행료를 확인한 후 이 방을 방문처리 할 지 말지가 정해진다. 통행료가 부족해서 통과할 수 없으면 재귀함수를 탈출시키고 통과할 수 있으면 연결된 다음 방 (next)을 dfs로 탐색한다. 

그리고 현재의 경로를 선택하지 않는 경우도 있을 수 있으니 다시 visited[now] = False 로 백트래킹 한다. 

from collections import deque, defaultdict
def dfs(now, total_money):
    global flag, visited
    x = graph[now][0]
    money = int(graph[now][1])
    next_rooms = list(map(int, graph[now][2:-1]))
    if x == 'E':  # empty room
        total_money += money
    elif x == 'L':
        if total_money <= money:
            total_money = money
    else:  # T
        if total_money >= money:
            total_money -= money
        else:
            return
    if now == n:
        flag = True
        return
    visited[now] = True # 통과할 수 있는 경우만 True 체크하기
    for next in next_rooms:
        if not visited[next]: # 방문하지 않은 노드 탐색하기
            dfs(next, total_money)
    visited[now] = False # 이번 노드를 방문하지 않는 경우, 다른 경로도 고려하기 (Back Tracking)


while True:
    n = int(input())
    if n == 0:
        break
    graph = defaultdict(list)
    for i in range(n):
        temp = list(input().split())
        graph[i+1] = temp

    visited = [False] * (n+1)
    flag = False
    dfs(1, 0) # start, total_money
    if flag:
        print("Yes")
    else:
        print("No")