[백준] 2310번 어드벤처 게임 자바 풀이

문제

입력과 출력

예제 입출력

---

🏅골드 4 짜리 문제이다.
다국어 문제라 번역에 조금 오류가 있었는지 처음엔 문제가 잘 이해가 안됐다.

문제 풀이 방법

• 각 방에 대한 정보를 저장할 클래스와 클래스 배열을 생성한다.

• N번째 줄 마다 N번 방에 대한 정보를 주는 문제이므로 각 줄을 입력받을 때 마다 해당 방에 대한 정보를 클래스 배열에 저장한다 (알파벳과 바로 뒤에 오는 숫자 두 가지가 클래스 배열에 저장된다).

• 세 번째 숫자와 0이 나오기 전까지의 숫자는 해당 방에서 이동할 수 있는 방의 번호를 나타내는 것이므로 ArrayList[] 배열을 생성해서 방끼리 이동 가능한 경로를 저장한다.

• dfs로 해당 방에 대한 조건을 만족하는 이동가능한 방을 이동하면서 끝방까지 도달하면 Yes를 출력한다.

전체 코드

package BFS;

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

public class Q2310 {
  static class Room{
      String K; //레프리콘의 방인지, 트롤의 방인지 판별
      int cost; //해당 방의 비용
      public Room(String K, int cost){
          this.K = K;
          this.cost = cost;
      }
  }

  static class Mine{
      int d, m; // d = 현재 내가 있는 방의 번호, m = 내가 소지하고 있는 돈 
      public Mine(int d, int m){
          this.d = d;
          this.m = m;
      }
  }

  static ArrayList<Integer>[] graph;
  static Room[] list;
  static boolean[] visited;

  static boolean bfs(int N){
      Queue<Mine> q = new LinkedList<>();
      visited[1] = true;
      q.offer(new Mine(1, 0));

      while(!q.isEmpty()){
          Mine cur = q.poll();
          int d = cur.d;
          int m = cur.m;

          if(d==N) return true;

          for(int v : graph[d]){
              String s = list[v].K;
              int cost = list[v].cost;

              switch (s) {
                  case "E":
                      if(!visited[v]){
                          q.offer(new Mine(v, m));
                          visited[v] = true;
                      }
                      break;
                  
                  case "L":
                      if(!visited[v]){
                          if(m<cost) m=cost;
                          q.offer(new Mine(v, m));
                          visited[v] = true;
                      }
                      break;

                  case "T":
                      if(!visited[v] && m>=cost){
                          q.offer(new Mine(v, m-cost));
                          visited[v] = true;
                      }
                      break;
                  default:
                      break;
              }
          }
      }
      return false;
  }

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();

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

          if(N==0) break;
      
          graph = new ArrayList[N+1];
          list = new Room[N+1];
          visited = new boolean[N+1];
  
          for(int i=1; i<=N; i++) graph[i] = new ArrayList<>();
          
          for(int i=1; i<=N; i++){
              StringTokenizer st = new StringTokenizer(br.readLine());
              String K = st.nextToken();
              int c = Integer.parseInt(st.nextToken());
              
              list[i] = new Room(K, c);

              while(true){
                  int v = Integer.parseInt(st.nextToken());
                  if(v==0) break;

                  graph[i].add(v);
              }
          }

          sb.append(bfs(N) ? "Yes" : "No").append("\n");
      }

      System.out.println(sb);
      
  }
}