[BOJ / C++] #1697 숨바꼭질
문제풀이
처음에 dfs로 풀다가 멈추는 구간이 N==K일 때밖에 없으니깐 엄청나게.. 깊어지고 안 끝나서
bfs로 풀었다.
<수빈이의 위치, 걸린 시간> pair를 queue에 저장한다.
pop한 pair의 수빈이의 위치가 동생과 같아질 때 시간을 리턴하면 된다.
시간이 적은 거 부터 시작해서 큐에 들어가므로 처음 나온 게 가장 빠른 시간이다.
동생을 찾기 전 까진 3가지의 경우를 모두 큐에 차례대로 넣어주면서 진행하면 된다! while(!q.empty())..
이 문제에서도 최단 거리로 가야 하기 때문에 visited
를 이용해 방문 하지 않았던 곳만 다시 큐에 넣도록 한다.
코드
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100000
int visited[MAX+1];
int bfs(int N,int K) {
queue<pair<int, int>> q; // 수빈이 위치, 시간
q.push(make_pair(N, 0));
visited[N] = true;
while (!q.empty()) {
int loc = q.front().first;
int time = q.front().second;
q.pop();
// 동생을 찾았을 때
if (loc == K)
return time;
// 3가지 경우
// 방문하지 않은 곳만! (방문한 곳에 다시 가면 최단 거리 X)
if (loc - 1 >= 0 && !visited[loc - 1]) {
q.push(make_pair(loc - 1, time + 1));
visited[loc - 1] = true;
}
if (loc + 1 <= MAX && !visited[loc + 1]) {
q.push(make_pair(loc + 1, time + 1));
visited[loc + 1] = true;
}
if (loc * 2 <= MAX && !visited[loc * 2]) {
q.push(make_pair(loc * 2, time + 1));
visited[loc * 2] = true;
}
}
}
int main(){
int N,K;
cin>>N>>K;
cout<<bfs(N,K)<<"\n";
return 0;
}
Author And Source
이 문제에 관하여([BOJ / C++] #1697 숨바꼭질), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inryu/BOJ-C-1697-숨바꼭질저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)