[백준 / BOJ] 2310 어드벤처 게임 (Rust)

문제

출처 : https://www.acmicpc.net/problem/2310

2310번: 어드벤처 게임

1부터 n까지의 번호가 붙은 방이 있다.

각 방은 E,L,T로 이루어져 있는데, 각각이 의미는 아래와 같다.

E : 비어있는 방 -> 아무런 동작도 하지 않음.

L : 레프리컨의 방 -> 이 방에 진입했을때, 내가 갖고있는돈이 방의 돈 보다 작다면, 방의 돈으로 내 돈이 맞춰짐.

T : 트롤의 방 -> 이 방에 진입하려면, 이 방의 돈 만큼 내가 돈을 갖고있어야 한다.

 

이 때, 1번방에서 n번방에 도달할 수 있다면, Yes, 아니라면 No를 출력하는 문제다.

---

풀이

BFS & DFS 알고리즘의 방문 배열에 금액 이라는 개념을 추가해서 풀면 되는 문제다.

금액 이라는 개념이 있기때문에, 다익스트라 알고리즘을 생각할 수 있는데, 이 문제는 입력이 작아서, 최소힙을 사용하지 않고, BFS DFS로 풀어도 풀리게 된다.

 

check배열에 다음과 같은 정보가 저장된다 가정하자.

check[idx] = idx에 도달했을때 갖고있는 돈의 최대 양

 

이 때, 기존의 "이미 방문했다면 재방문 하지 않는" 조건을 "이전에 방문한 금액이 지금 방문한 금액보다 크거나 같다면, 방문하지 않는" 조건으로 수정해서 풀 수 있다.

 

나머지는 기본적인 BFS & DFS를 적용하면 된다.

 

의사코드

if(check[idx] >= current_cost) continue;

 

주요 소스코드

fn is_reachable(case: i32, maze: Vec<(char, i32, Vec<i32>)>) -> bool {
    let mut check: Vec<i32> = Vec::new();
    for _i in 0..case+1 {
        check.push(-1);
    }
    let mut status_deq: VecDeque<(i32, i32)> = VecDeque::new();
    status_deq.push_back((1, calc_cost(1,0, &maze)));
    while !status_deq.is_empty() {
        let current_status = status_deq.pop_front().unwrap();
        if current_status.0 == case {
            return true;
        }
        if check[current_status.0 as usize] >= current_status.1 {
            continue;
        }
        check[current_status.0 as usize] = current_status.1;
        for i in &maze[current_status.0 as usize].2 {
            let next_cost = calc_cost(*i, current_status.1, &maze);
            if check[*i as usize] > next_cost {
                continue;
            }
            status_deq.push_back((*i, next_cost));
        }
    }
    return false;
}

 

다익스트라로 풀릴거 같기는 한데, 다익스트라는 정렬과정이 있어서, 뭐가 빠른지는 해봐야 알 거 같다.

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/2310%20어드벤처%20게임/main.rs

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃