백준 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

 

풀이

아니 좀. 그렇다.

반복 방문하면 안된다는 지문도 없을 뿐 더러 문제는 미로의 탈출을 얘기하면서 정답은 N번방에 도착할 수 있는지를 묻고있다.

반복 방문 하는 건 테케 돌려보다가 스택오버플로우 나서 보니까 계속 돌더라. 아니 이게 무슨..

여러모로 갸우뚱하게 만들었던 문제, 그냥 DFS로 탐색했다.

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

public class BJ_2310_어드벤처게임 {
    public static class Room{
        char type;
        int value;
        List<Integer> door;
        boolean visited=false;
        public Room(char type, int value, List<Integer> door,boolean visited)
        {
            this.type = type;
            this.value = value;
            this.door = door;
            this.visited = visited;
        }
    }
    static int N;
    static List<Room> list;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            if(N == 0) break;

            //맵 정보 받을 준비
            list = new ArrayList<>();
            for(int i=0; i<N; i++)
            {
                result=0;
                List<Integer> roomList = new ArrayList<>();
                st = new StringTokenizer(br.readLine());
                char t = st.nextToken().charAt(0);
                int v = Integer.parseInt(st.nextToken());
                while(true)
                {
                    int check = Integer.parseInt(st.nextToken());
                    if(check==0) break;
                    roomList.add(check-1);
                }

                list.add(new Room(t,v,roomList,false));
            }
            DFS(0,0);
            System.out.println(result==1?"Yes":"No");
        }
    }

    public static void DFS(int start, int gold)
    {
        if(list.get(start).type=='T') gold-=list.get(start).value;
        else {
            if(gold < list.get(start).value)
                gold+=list.get(start).value;
        }

        if(gold>=0)
        {
            if(start+1==N){
                result = 1;
                return;
            }
            list.get(start).visited=true;
            for(int i=0; i<list.get(start).door.size();i++)
            {
                if(!list.get(list.get(start).door.get(i)).visited)
                    DFS(list.get(start).door.get(i),gold);
            }
            list.get(start).visited=false;
        }
        else
        {
            if(list.get(start).type=='T') gold += list.get(start).value;
            return;
        }
    }
}