백준1927 (SILVER 1) - 숨바꼭질
Published:
틀린 풀이
좌표를 한칸씩 앞으로, 뒤로 혹은 2배 가능. -> 3가지 경우를 고려한 방식으로 DP로 풀었다. but 시간 초과.
이유는 DP 방식으로 터무니 없는 방식(예를 들어 1부터 10만까지 다 +1) 까지 고려하기에.
정답
정답으로 향하는 핵심은 ‘가장 빠른 시간’ = 최단 거리. => BFS 이용. 각 단계에 가능한 && 가장 빨리 해당 칸에 도달한 경우만 고려 = 복잡도가 준다.
//시간 초과...
//처음에 DP로 접근했으나 시간이...
//최단 거리 찾는 BFS 문제였다.
//BFS는 짧은 거리 케이스가 먼저 처리되서 빠를 것.
//DP는 깊이 우선 탐색 처럼 작동해, 말도 안되는 케이스까지 일단 다 계산후 갱신할테니 느릴 것.
#include<iostream>
#include<deque>
#include<tuple>
bool visit[100001];
int s, e;
int main() {
for(int i = 0; i<=100000; i++){
visit[i] = false;
}
std::cin >> s >> e;
std::deque<std::tuple<int,int>> q;
q.push_back(std::make_tuple(s,0));
visit[s] = true;
while(true){
int posi, turn;
std::tie(posi,turn) = q.front();
visit[posi] = true;//이걸 안했네.. 처음에 visit 배열 추가할때 부터 이를 어떻게 관리할지 생각하고 처리해 줬어야지...
q.pop_front();
if(posi == e){
std::cout << turn;
return 0;
}
if(posi+1 >=0 && posi+1 <= 100000 && !visit[posi+1]){
q.push_back(std::make_tuple(posi+1,turn+1));
}
if(posi-1 >=0 && posi-1 <= 100000 && !visit[posi-1]){
q.push_back(std::make_tuple(posi-1,turn+1));
}
if(posi*2 >=0 && posi*2 <= 100000 && !visit[posi*2]){
q.push_back(std::make_tuple(posi*2,turn+1));
}
}
}
단순 구현 실수
- visit을 표시 안해줘서 계속 스택 오버 플로가 났었다. => BFS 고려할 것 (방문해서 visit 표시, 방문시 visit 하지 않았고, 문제만의 방문할 조건을 만족하는지, 유효한 인덱스인지.) 조심!
이외
- DP 풀이도 된다곤한다. 담에 시간나면 한번 찾아봐도 괜찮을지도?
