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

입구(1)에서 목적지(N)까지 이동할 수 있는지 찾는 문제입니다.

BFS를 사용해서 탐색했습니다.
갈 수 있는 방향으로 모두 이동하며 visit배열을 두어서
이전보다 나은 상황에만 중복된 이동을 허용해 주었습니다.

신경 쓴 사항으로는

하나의 케이스가 끝났을 때 변수 값 초기화 해주기
visit배열을 int로 받아서 이전보다 돈을 많이 가진 경우에만 탐색할 수 있게 해주기

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = null;

    int size;
    ArrayList<ArrayList<Integer>> al;
    int[] visit;

    while (true) {
      st = new StringTokenizer(br.readLine());
      size = Integer.parseInt(st.nextToken());
      al = new ArrayList<>();
      visit = new int[size + 1];

      if (size == 0) {
        break;
      }

      for (int i = 0; i <= size; ++i) {
        ArrayList<Integer> temp = new ArrayList<>();
        al.add(temp);
        visit[i] = -1;
      }

      for (int i = 1; i <= size; ++i) {
        st = new StringTokenizer(br.readLine());

        String s = st.nextToken();
        int type = s.equals("E") ? 0 : s.equals("L") ? 1 : 2;
        int value = Integer.parseInt(st.nextToken());
        al.get(i).add(type);
        al.get(i).add(value);
        while (true) {
          int next = Integer.parseInt(st.nextToken());
          if (next == 0) {
            break;
          }

          al.get(i).add(next);
        }
      }

      Queue<Pair> q = new LinkedList<>();
      String result = "No";

      if (al.get(1).get(0) != 2) {
        q.add(new Pair(1, al.get(1).get(1)));
      }
      while (!q.isEmpty()) {
        int index = q.peek().index;
        int money = q.peek().money;
        q.poll();

        for (int i = 2; i < al.get(index).size(); ++i) {
          int next = al.get(index).get(i);
          int type = al.get(next).get(0);
          int value = al.get(next).get(1);

          int nextMoney = 0;
          if (type == 1) {
            nextMoney = Math.max(money, value);
          } else {
            nextMoney = money - value;
          }

          if (visit[next] >= nextMoney || nextMoney < 0) {
            continue;
          }

          if (next == size) {
            result = "Yes";
            while (!q.isEmpty()) {
              q.poll();
            }
            break;
          }

          visit[next] = nextMoney;
          q.add(new Pair(next, nextMoney));
        }
      }
      bw.write(result + "\n");
    }
    bw.close();
  }

  static public class Pair {
    int index;
    int money;

    public Pair(int index, int money) {
      this.index = index;
      this.money = money;
    }
  }
}