알고리즘 :: 백준 :: BFS :: 13549 :: 숨바꼭질3
문제
문제접근
문제 이해
알고리즘 :: 백준 :: BFS :: 1697 :: 숨바꼭질 (velog.io) 문제의 연장입니다.
- 저번 문제와 차이점은 단 하나입니다. 순간이동이 1초 → 0초로 바뀌었습니다.
해결 1
- 이 문제는
1697번
풀이에서 순간이동에 대한 코드에서push()
할 때 시간을 더해주지 않는 것으로 바꾸기만 하면 AC를 받을 수 있습니다. - 왜냐하면 제가 세 액션 중 순간이동을 가장 먼저 조건문에 넣었기 때문입니다.
- 즉, 우연에 의한 AC입니다. 정식 풀이는 해결 2가 맞습니다.
해결 2
- 우리가 BFS를 이용해서 최소시간/최단거리 문제를 풀 수 있는 이유는 가중치가 1이라는 것이 보장되기 때문입니다.
- 앞으로 이동해도, 뒤로 이동해도 심지어 순간이동을 하더라도 이전까지는 1초만 소요됐지만, 이제는 순간이동은 가중치가
0
입니다. - 따라서 같은 임의의 점
x
라고 할지라도, 가중치1
로 온 것과 가중치0
으로 온 것은 다르므로 서로 다른 점이라고 판단해야 합니다.- 왜냐하면, 1초 소요해서 도착한
x
와 0초 소요해서 도착한x
를 기존의queue
로는 구분할 수 없기 때문입니다. - 따라서 이 문제는 가중치 0에 대한
queue
와 가중치 1에 대한queue
2개를 사용해야 하는 문제입니다. - 우리는
deque
이라는 자료구조가queue
를 앞뒤로 합쳐놓은 형태의 자료구조임을 알고있습니다. - 따라서 이 문제는
deque
자료구조를 사용해서 가중치가 0일 때는push_front()
를, 가중치가 1일 때는push_back()
을 하는 방식으로 풀이합니다.
- 왜냐하면, 1초 소요해서 도착한
deque
의 앞쪽에는 가중치가 0인 행동들이 들어가므로 가장 먼지 목표지점K
에 도착하면 loop를 탈출해도 됩니다.- 우리는 이번 문제를 통해 가중치가 0 또는 1인 최단거리/최소시간 문제에서는 BFS를 사용하되
queue
가 아닌deque
을 사용해야한다는 점을 배울 수 있습니다.
코드
#include <iostream>
#include <deque>
#define MAX 100001
using namespace std;
int N, K;
bool visited[MAX];
int solve() {
deque<pair<int,int>> q;
q.push_front({N, 0});
while(!q.empty()){
int pos = q.front().first, t = q.front().second;
if(pos == K) return t;
int goPos = pos + 1, backPos = pos - 1, telePos = 2 * pos;
q.pop_front();
if(telePos < MAX && !visited[telePos]) // 순간이동
visited[telePos] = true, q.push_front({telePos, t});
if(backPos >= 0 && !visited[backPos]) // 한 칸 뒤로 이동
visited[backPos] = true, q.push_back({backPos, t + 1});
if(goPos < MAX && !visited[goPos]) // 한 칸 앞으로 이동
visited[goPos] = true, q.push_back({goPos, t + 1});
}
}
int main(){
cin >> N >> K;
cout << solve() << '\n';
}
결과
Author And Source
이 문제에 관하여(알고리즘 :: 백준 :: BFS :: 13549 :: 숨바꼭질3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@embeddedjune/알고리즘-백준-BFS-13549-숨바꼭질3-07d6qtc3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)