[백준]2310: 어드벤처 게임(java)

문제

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

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

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

입력

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

출력

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

예제 입력 1 

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

예제 출력 1 

No
Yes

---

풀이

처음엔 bfs로 생각하였는데 뎁스가 넓어지고 깊어지며 메모리초과가 발생하였다.

백트래킹 + dfs를 섞어서 다시 풀이하였다.

각 방에서 다음 방으로 갈 수 있는 번호를 담는 리스트

그 방에서 요구하는 돈을 담은 배열

그 방의 종류를 담은 배열을 선언하여 관리하였다.

 

전체코드

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

public class BJ_G5_2310_어드벤처게임 {
    static ArrayList<Integer>[] nextRoom;
    static char[] rooms;
    static int[] getMoney;
    static int N;
    static boolean isFinished;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder ans = new StringBuilder();
        N = 0;
        while((N = Integer.parseInt(br.readLine())) != 0) {
            rooms = new char[N+1];
            nextRoom = new ArrayList[N+1];
            getMoney = new int[N+1];
            visited = new boolean[N+1];
            for(int i=1; i<=N; i++) {
                st = new StringTokenizer(br.readLine());
                rooms[i] = st.nextToken().charAt(0);
                getMoney[i] = Integer.parseInt(st.nextToken());
                nextRoom[i] = new ArrayList<>();
                int roomNum = 0;
                while((roomNum = Integer.parseInt(st.nextToken())) != 0) {
                    nextRoom[i].add(roomNum);
                }
            }
            isFinished = false;
            dfs(1, 0);
            if(isFinished) ans.append("Yes\n");
            else ans.append("No\n");
        }
        System.out.printf(ans.toString());
    }

    private static void dfs(int room, int money) {
        if(isFinished) return;
        if(room == N) {
            isFinished = true;
            return;
        }

        for(int nRoom: nextRoom[room]) {
            if(visited[nRoom]) continue;
            if(rooms[nRoom] == 'L') {
                if(getMoney[nRoom] > money) {
                    money = getMoney[nRoom];
                }
            } else if(rooms[nRoom] == 'T') {
                if(getMoney[nRoom] <= money) {
                    money -= getMoney[nRoom];
                } else {
                    return;
                }
            }
            visited[nRoom] = true;
            dfs(nRoom, money);
            visited[nRoom] = false;
        }
        return;
    }
}