문제
출처 : https://www.acmicpc.net/problem/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
'알고리즘 (2020 : 08 : 10 ~ ) > BFS,DFS' 카테고리의 다른 글
[백준 / BOJ] 2251 물통 (cpp) (0) | 2023.02.10 |
---|---|
[백준 / BOJ] 18809 Gaaaaaaaaaarden (Java) (0) | 2022.06.03 |
[백준 / BOJ] 14442 벽 부수고 이동하기 2 (Java) (0) | 2022.05.15 |
[백준 / BOJ] 1765 닭싸움 팀 정하기 (Java) (0) | 2021.08.30 |
[백준 / BOJ] 5827 What's Up With Gravity (0) | 2021.05.14 |