[ Baekjoon - 10/06 ] - 2310번: 어드벤처 게임

• 문제 링크 : https://www.acmicpc.net/problem/2310

2310번: 어드벤처 게임

 

• 소요 시간 : 40분

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 128MB
   • 문제
     • 방의 개수 N개(1≤N≤1,000), 방별 비용(0≤N≤500), 방의 유형은 빈방, 레프리콘방, 트롤방임
     • 1번방에서 N번방으로 갈 수 있는지 여부를 출력하는 문제이고, 방의 경우에 따라 갈수있는지 불가능한지 정해진다
     • 빈방은 변화가 없고, 레프리콘방은 일정금액 이하일경우 돈을 일정금액이 되도록 도와주고, 트롤방은 통행세를 내야한다는 규칙?이 있다.
   • 이해
     • 첫번째 방이 1번이라는걸 문제에서 직관적으로 주질않아 0번방시작인지 1번방시작인지 찾아본거 말고는, 문제가 단순해서 있는 그대로 이해가 가능했다. 문제에서 직관적으로 1번방에서 시작한다고 줬었으면...ㅠ
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 1번방 시작인지 0번방 시작인지를 알기위해 예제를 따라가보았다.
   • 쭉 나열하며 가능여부를 따져본 결과 갈수있는곳을 차례차례 방문하며 다녔을때 끝까지 갈 수 있는 경우가 있으면 Yes를 출력하면 될것같았다.
3. 문제를 어떻게 해결할 것인가
   • 2번에서와 같이 결국 끝까지 가야하므로 DFS든 BFS든 가능하다고 생각했다.
     (시간과 N의 범위를 고려해도 가능)
4. 위 계획을 검증
   • 완탐이기 때문에 넘어가겠다.
5. 계획 수행 (실제코드 작성)
   1. Java 11 - 나는 DFS로 풀었다.

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static int N;
            static Room[] rooms;
            static LinkedList<Integer>[] adjList;
            static boolean[] vis;
            static boolean flag;
            static int money;
        
            public static void main(String[] args) throws Exception {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                while(true) {
                    N = Integer.parseInt(br.readLine());
                    if(N == 0) {
                        break;
                    }
                    
                    adjList = new LinkedList[N+1];
                    rooms = new Room[N+1];
                    vis = new boolean[N+1];
        
                    money = 0;
                    flag = false;
        
                    for(int i=1; i<=N; i++) {
                        adjList[i] = new LinkedList<Integer>();
                    }
        
                    for(int n=1;n<=N; n++) {
                        StringTokenizer st = new StringTokenizer(br.readLine());
        
                        char npc = st.nextToken().charAt(0);
                        int cost = Integer.parseInt(st.nextToken());
        
                        rooms[n] = new Room(npc, cost);
                        while(true) {
                            int num =  Integer.parseInt(st.nextToken());
                            if(num == 0) {
                                break;
                            }
                            if(num == n) {
                                continue;
                            }
                            adjList[n].add(num);
                        }
                    }
                    dfs(1);
                    System.out.println(flag?"Yes":"No");
                }
            }
        
            static void dfs(int roomIdx) {
                if(rooms[roomIdx].npc == 'T') {
                    if(rooms[roomIdx].cost <= money) {
                        money -= rooms[roomIdx].cost;
                    }else {
                        return;
                    }
                }
                if(roomIdx == N) {
                    flag = true;
                    return;
                }
        
                if(rooms[roomIdx].npc == 'L') {
                    if(rooms[roomIdx].cost > money) {
                        money = rooms[roomIdx].cost;
                    }
                }
        
                vis[roomIdx] = true;
                for(int n : adjList[roomIdx]) {
                    if(!vis[n]) {
                        dfs(n);
                    }
                }
                vis[roomIdx] = false;
        
            }
            static class Room{
                char npc;
                int cost;
        
                public Room(char npc, int cost) {
                    this.npc = npc;
                    this.cost = cost;
                }
            }
        }

         

• 결과