2310 - 어드벤처 게임 (Java)

🔗 문제 링크

---

📌 문제 설명

• N개의 방이 있으며, 각 방에는 특정한 규칙이 존재한다.
• 1번 방에서 시작하여 N번 방에 도착하는 것이 목표.
• 방의 종류는 다음과 같다:
  • L (Leprechaun, 요정): 최소 X 골드가 필요하며, 만약 부족하면 X 골드로 채워줌.
  • T (Troll, 트롤): X 골드가 필요하며, 부족하면 입장 불가. 입장 시 X 골드를 차감.
  • E (Empty, 빈 방): 별다른 제한 없이 입장 가능.
• 각 방에서 이동할 수 있는 다음 방들의 정보가 주어짐.

목표: 1번 방에서 시작하여 N번 방에 도달할 수 있는지 판별하는 문제.

---

💡 접근 방식

🔹 1️⃣ DFS를 사용한 탐색

• 시작점 1부터 DFS 탐색을 수행.
• 각 방의 규칙에 따라 입장이 가능한지 확인 후, 탐색을 계속 진행.
• 도착점 N에 도달하면 Yes, 도달하지 못하면 No를 출력.

🔹 2️⃣ 방의 유형에 따른 처리

1. 요정(L)
   • 만약 현재 가진 골드가 X보다 적다면, X로 충전.
2. 트롤(T)
   • 만약 X 골드보다 적다면 해당 경로 탐색 종료.
   • 아니라면 X를 차감한 후 탐색 진행.
3. 빈 방(E)
   • 바로 이동 가능.

🔹 3️⃣ 방문 처리 (visited)

• 방문한 노드는 true로 체크, DFS 탐색을 진행.
• 한 번 지나간 방이라도, 더 많은 골드로 방문할 수 있다면 다시 탐색해야 함.
  (이 부분을 해결하기 위해 visited 배열을 관리하면서 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 Main {
    private static StringTokenizer st;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N;
    private static String[] map;
    private static boolean isPossible;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        while (setting() != 0) {
            visited[1] = true;
            dfs(1, 0);
            System.out.println((isPossible) ? "Yes" : "No");
        }
    }

    private static void dfs(int cur, int money) {
        st = new StringTokenizer(map[cur]);
        String type = st.nextToken();
        int moneyValue = Integer.parseInt(st.nextToken());

        List<Integer> nextPoints = new ArrayList<>();
        while (st.hasMoreTokens()) {
            int next = Integer.parseInt(st.nextToken());
            if (next != 0) nextPoints.add(next);
        }

        // 🏰 방에 입장할 수 있는 조건
        if (type.equals("L")) {
            if (money <= moneyValue) money = moneyValue; // 골드가 부족하면 충전
        } else if (type.equals("T")) {
            if (money < moneyValue) return; // 골드 부족하면 이동 불가
            money -= moneyValue; // 골드 차감
        }

        // 도착점 확인 (N번 방 도달)
        if (cur == N) {
            isPossible = true;
            return;
        }

        // 다음 방으로 이동
        for (int nextPoint : nextPoints) {
            if (visited[nextPoint]) continue;
            visited[nextPoint] = true;
            dfs(nextPoint, money);
            visited[nextPoint] = false;
        }
    }

    private static int setting() throws IOException {
        N = Integer.parseInt(br.readLine());
        if (N == 0) return N;

        isPossible = false;
        map = new String[N + 1];
        visited = new boolean[N + 1];

        for (int i = 1; i < N + 1; i++) {
            map[i] = br.readLine();
        }
        return N;
    }
}

---

✅ 코드 분석

기능	설명
dfs(cur, money)	현재 방 cur에서 money를 가지고 탐색
visited[]	방문 여부를 체크하여 무한 루프 방지
setting()	입력을 받아서 map[] 배열에 저장

---

🚀 시간복잡도 분석

• N ≤ 100 이므로 DFS(깊이 우선 탐색)로 충분히 해결 가능.
• 최악의 경우 O(N^2) 탐색이 되지만, 문제에서 주어진 조건 내에서는 실행 가능.

---

🔧 최적화 및 개선점

1️⃣ 방문 처리 (visited[]) 최적화

현재 코드에서는 같은 방을 여러 번 방문하는 경우에도 visited[]를 계속 변경하지만,
더 많은 골드를 가지고 방문하는 경우도 고려해야 한다.

✅ 해결 방법: visited 배열을 최대 골드 상태를 저장하는 방식으로 변경하면 불필요한 탐색을 줄일 수 있음.

private static int[] maxMoney;

private static void dfs(int cur, int money) {
    if (maxMoney[cur] >= money) return; // 현재 방문한 방의 골드 상태가 더 높으면 탐색 불필요
    maxMoney[cur] = money; // 현재 골드 상태 업데이트
    ...
}

🚀 이렇게 하면 불필요한 재탐색을 줄여 성능을 향상시킬 수 있음.

해당 visited[] 방문처리를 int를 사용해서 진행하는 것이 효율적으로 보여서 진행. 탐색을 진행할때의 탐색지점을 이전에 방문했을때의 돈보다 적거나 같은 경우라면 탐색하지 않는 것으로 진행.
▶ 결과는 메모리초과가 발생, boolean에서 int로 변형한것의 차이가 원인이라고 생각.

---

💔 문제의 오류?

visited[]을 int[]형으로 처리하던 중에 문득, a에서 b를 탐색한뒤 다시 a를 되돌아가는 경우가 어떻게되는지 궁금해서 테스트케이스를 진행해봤더니 정확한 답이 도출되지 않았다.

4
E 0 2 0
E 0 3 4 0
L 10 2 0
T 10 2 0
0

해당 테스트케이스를 보면 3번문을 방문한뒤 2번을 다시 방문하고 4번을 가는 경우가 만족되는데 정답코드로 진행하면 false를 도출한다. 추가적인 케이스가 필요해보이고, 게시판에도 언급되어있는 부분이었음.

---

🎯 결론

✅ DFS를 사용하여 모든 경우 탐색
✅ 골드 상태에 따라 이동 가능 여부 결정
✅ visited[]를 최적화하여 탐색을 줄일 수 있음