BOJ : 1697 숨바꼭질 (C++)
문제
Code
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int dist[200002];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
queue<int> Q;
int N, K;
cin >> N >> K;
if(N == K)
{
cout << 0 ;
return 0;
}
fill(dist, dist+200000,-1);
dist[N] = 0;
Q.push(N);
while(!Q.empty())
{
auto cur = Q.front(); Q.pop();
int dx[3]={-1, +1, cur};
for(int dir=0;dir<3;dir++)
{
int nx = cur +dx[dir];
if(nx < 0 || nx > 200000) continue;
if(dist[nx] != -1) continue;
dist[nx] = dist[cur] + 1;
Q.push(nx);
if(nx == K)
{
cout << dist[nx];
return 0;
}
}
}
}
- 아이디어의 핵심은 BFS를 1차원에서도 사용할 수 있다는 생각
- 1차원이든 / 2차원이든 정점사이의 거리를 구할 때 BFS를 사용할 수 있다는 생각!
- 값이 변할 수 있는 범위(-1 / +1 / 2*cur)은 dx[3]으로 해결
[ 주의 ]
이 문제는 운 좋게 수빈이가 100,000 이하에서 움직이는게 가장 효율적이지만, 이렇게 값에 변화를 추구하는 상황에서 반드시 입력이 100,000 이하에서 처리될 것이라고 생각하지 않는것이 매우 중요!!!!!
(2배가 곱해져서 가장 효율적이 될 수 있기 때문에 200,000으로 잡았다)
Author And Source
이 문제에 관하여(BOJ : 1697 숨바꼭질 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-1697-숨바꼭질-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <iostream> #include <queue> #include <utility> using namespace std; int dist[200002]; int main() { ios::sync_with_stdio(0); cin.tie(0); queue<int> Q; int N, K; cin >> N >> K; if(N == K) { cout << 0 ; return 0; } fill(dist, dist+200000,-1); dist[N] = 0; Q.push(N); while(!Q.empty()) { auto cur = Q.front(); Q.pop(); int dx[3]={-1, +1, cur}; for(int dir=0;dir<3;dir++) { int nx = cur +dx[dir]; if(nx < 0 || nx > 200000) continue; if(dist[nx] != -1) continue; dist[nx] = dist[cur] + 1; Q.push(nx); if(nx == K) { cout << dist[nx]; return 0; } } } }
- 아이디어의 핵심은 BFS를 1차원에서도 사용할 수 있다는 생각
- 1차원이든 / 2차원이든 정점사이의 거리를 구할 때 BFS를 사용할 수 있다는 생각!
- 값이 변할 수 있는 범위(-1 / +1 / 2*cur)은 dx[3]으로 해결
[ 주의 ]
이 문제는 운 좋게 수빈이가 100,000 이하에서 움직이는게 가장 효율적이지만, 이렇게 값에 변화를 추구하는 상황에서 반드시 입력이 100,000 이하에서 처리될 것이라고 생각하지 않는것이 매우 중요!!!!!
(2배가 곱해져서 가장 효율적이 될 수 있기 때문에 200,000으로 잡았다)
Author And Source
이 문제에 관하여(BOJ : 1697 숨바꼭질 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-1697-숨바꼭질-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)