[백준] 2310 어드벤처 게임 - Java

 

 

 

문제 출저

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

2310번: 어드벤처 게임

 

 

 

 

문제

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

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

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

 

 

입력

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

 

 

 

출력

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

 

 

 

문제 풀이

Room 정보를 저장한다. 

DFS를 통해 1부터 탐색을 시작한다. 

방의 요금을 처리한 다음 다음 방을 탐색한다. 

visited를 사용하여 방의 방문 처리를 관리한다. 

n에 도착했을 때 돈이 남아있다면 Yes, 아니면 No를 저장한다. 

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
어드벤쳐 게임
https://www.acmicpc.net/problem/2310

 */

public class Main {

    static int n;
    static StringBuilder sb;
    static Map<Integer, Room> rooms;

    static boolean[] visited;
    static boolean flag;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        while(true) {
            n = Integer.parseInt(br.readLine());

            if (n == 0) {
                System.out.println(sb.toString());
                return;
            }

            rooms = new HashMap<>();
            for (int i = 1; i < n+1; i++) {
                String[] s = br.readLine().split(" ");

                char type = s[0].charAt(0);
                int cost = Integer.parseInt(s[1]);


                List<Integer> nextRoom = new ArrayList<>();
                for (int j = 2; j < s.length - 1; j++) {
                    nextRoom.add(Integer.parseInt(s[j]));
                }

                Room room = new Room(type, cost, nextRoom);
                rooms.put(i, room);
            }

            solution();

        }

    }

    // 탐색 시작
    public static void solution() {

        visited = new boolean[n + 1];
        visited[1] = true;
        flag = false;

        dfs(1, 0);

        if (flag) sb.append("Yes").append("\n");
        else sb.append("No").append("\n");

    }


    // 탐색
    public static void dfs(int start, int cost) {

        if (flag) return;

        Room room = rooms.get(start);

        // 금액 계산
        if (room.type == 'L') {
            cost = Math.max(cost, room.cost);
        }
        else if (room.type == 'T') {
            cost -= room.cost;
            if (cost < 0) return;
        }

        if(start == n) {
            flag = true;
        }

        // 다음 방 탐색
        for (int roomNumber : room.nextRoom) {

            if (visited[roomNumber] == false) {
                visited[roomNumber] = true;
                dfs(roomNumber, cost);
                visited[roomNumber] = false;
            }
        }

    }



    public static class Room {
        char type;
        int cost;
        List<Integer> nextRoom;

        Room(char type, int cost, List<Integer> nextRoom) {
            this.type = type;
            this.cost = cost;

            this.nextRoom = new ArrayList<>();
            this.nextRoom.addAll(nextRoom);
        }
    }

}