[백준] 2310번 어드벤처 게임 (JAVA)

문제

- 1번 방에서 출발해서 n번 방으로 도착이 목표

- 갈 수 있다면 Yes, 갈 수 없다면 No 출력

- 각 방 안에는 번호가 붙은 문이 있을 수 있고, 각 문은 해당하는 번호의 방으로 통함

- 방 안에는 레프리콘이나 트롤이 있을 수도 있음

- 레프리콘이 있는 방에 들어가면 소지금이 일정 양 이하로 떨어지지 않게 채워줌 (일정량 미만이면 그만한 양이 되도록 채워주고, 이상이면 그대로 둠)

- 트롤이 있는 방에 들어가면 일정량의 통행료를 지불해야 함

 

해결방법

방문한 곳을 체크하면 각 방을 DFS로 탐색하여 목표하는 방까지 탐색하였다. 문제에 제시된 조건에 따라 레프리콘과 트롤을 만났을 때, 조건을 처리해주었으며 소지금이 바닥나면 해당 함수를 탈출할 수 있게 구현하였으며, 재귀적으로 탐색할 수 있도록 구현하였다. 다시 오랜만에 문제를 풀어서 그런가 시간이 조금 오래 걸렸지만, 다시 열심히 달려야겠다 !

 

코드

import java.io.*;
import java.util.*;

// 방 정보
class Room{
    String roomType;		// 방 타입
    int amount;			// 금화
    ArrayList<Integer> canGo;	// 갈 수 있는 방
    boolean visit;		// 방문 여부

    public Room(String roomType, int amount, ArrayList<Integer> canGo) {
        this.roomType = roomType;
        this.amount = amount;
        this.canGo = canGo;
    }
}

public class Main {
    static boolean result;		// 결과 출력을 위한 flag
    static int n;			// 방의 개수
    static Room[] rooms;		// 방 정보
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true){
            result = false;
            n = Integer.parseInt(br.readLine());
            if(n == 0) break;		// 0이 입력되면 종료
            rooms = new Room[n];	// 방 정보 초기화
            // 방 정보 입력
            for(int i = 0; i<n; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                String roomType = st.nextToken();
                int amount = Integer.parseInt(st.nextToken());
                ArrayList<Integer> canGo = new ArrayList<>();
                while (st.hasMoreTokens()){
                    canGo.add(Integer.parseInt(st.nextToken()));
                }
                // 마지막 0은 방 정보에 들어가지 않기 때문에 지워줌
                canGo.remove(canGo.size()-1);
                rooms[i] = new Room(roomType, amount, canGo);
            }
            // 방 탐색
            move(0, 0);
           // 탐색 결과에 따라 출력
            if(!result){
                System.out.println("No");
            }
        }
    }

    static void move(int start, int money){
    	// 트롤을 만나면 돈 빼앗김
        if(rooms[start].roomType.equals("T")) money -= rooms[start].amount;
        // 트롤을 만나지 않으면 일정량 이상의 소지금을 채울 수 있음
        else{
            if(money < rooms[start].amount){
                money = rooms[start].amount;
            }
        }
		
        // 돈이 0원 이상이면
        if(money >= 0){
        	// 마지막 방에 도착했으면 Yes 출력 가능
            if(start + 1 == n){
                System.out.println("Yes");
                result = true;
            }
			
            // 방문 처리
            rooms[start].visit = true;
			
            // 방문하지 않은 다음 방들에 대해서 방문하는 재귀함수 실행
            for(int i = 0; i<rooms[start].canGo.size(); i++){
                if(!rooms[rooms[start].canGo.get(i)-1].visit){
                    move(rooms[start].canGo.get(i)-1, money);
                }
            }
            
            rooms[start].visit = false;

        }
		
        // 트롤을 만났을 때 깎였던 돈 복구
        else {
            if(rooms[start].roomType.equals("T")) money += rooms[start].amount;
            return;
        }
    }
}