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

1. 문제

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

2310번: 어드벤처 게임

 

 

2. 풀이 과정

자주 풀어왔던 2차원 배열의 dfs가 아니라 다음에 갈 좌표가 주어지는 dfs 문제이다.

백트래킹할 때, 가격은 원래 값을 보장해줘야 하므로 temp라는 변수를 추가로 사용하여 구현하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static Miro[] miros;
    static boolean[] visited;
    static String result;

    public static class Miro{
        char content;
        int cost;
        ArrayList<Integer> doors;

        public Miro(char content, int cost){
            this.content = content;
            this.cost = cost;
            this.doors = new ArrayList<>();
        }
    }

    public static void dfs(int money, int now){
        if(now==N){
            result = "Yes";
            return;
        }

        for(int door : miros[now].doors){
            if(visited[door]){continue;}

            int temp = money;
            switch (miros[door].content){
                case 'L':
                    temp = Math.max(temp, miros[door].cost);
                    break;
                case 'T':
                    temp -= miros[door].cost;
                    if(temp < 0){
                        continue;
                    }
                    break;
            }

            visited[door] = true;
            dfs(temp, door);
            visited[door] = false;
        }

    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        StringBuilder sb = new StringBuilder();
        while(true){
            N = Integer.parseInt(br.readLine());
            if(N==0){break;}

            miros = new Miro[N+1];
            visited = new boolean[N+1];
            for(int i=1; i<=N; i++){
                st = new StringTokenizer(br.readLine());
                miros[i] = new Miro(st.nextToken().charAt(0), Integer.parseInt(st.nextToken()));
                while(true){
                    int su = Integer.parseInt(st.nextToken());
                    if(su==0){break;}
                    miros[i].doors.add(su);
                }
            }
            result = "No";
            visited[1] = true;
            dfs(0, 1);
            sb.append(result).append("\n");
            //
        }
        System.out.println(sb);
    }
}

 

 

결과