BOJ : 13549 숨바꼭질3 - C++
숨바꼭질3
코드
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
int dx[3] = {2, -1, 1};
int board[200001];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
cin >> N >> K;
queue<int> q;
q.push(N);
board[N] = 1;
if(N == K){
cout << 0;
return 0;
}
while(!q.empty())
{
int cur = q.front(); q.pop();
for(int i=0;i<3;i++)
{
int nx;
if(i != 0) nx = cur + dx[i];
else nx = cur*dx[i];
if(nx < 0 || nx >= 200000 || board[nx] ) continue;
q.push(nx);
if(i != 0) board[nx] = board[cur] + 1;
else board[nx] = board[cur];
if(nx == K){
cout << board[nx] - 1 ;
return 0;
}
}
}
return 0;
}
- key point!
: 현재 값의 2배로 이동하는 cost가 0이기 때문에 가중치가 제일 높아야한다. --> 가장 먼저 이동하게 dx[] 조정!
(관련 반례 : 0,2 --> 1이 나와야 함!)
Author And Source
이 문제에 관하여(BOJ : 13549 숨바꼭질3 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-13549-숨바꼭질3-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <string> #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cmath> using namespace std; int dx[3] = {2, -1, 1}; int board[200001]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int N, K; cin >> N >> K; queue<int> q; q.push(N); board[N] = 1; if(N == K){ cout << 0; return 0; } while(!q.empty()) { int cur = q.front(); q.pop(); for(int i=0;i<3;i++) { int nx; if(i != 0) nx = cur + dx[i]; else nx = cur*dx[i]; if(nx < 0 || nx >= 200000 || board[nx] ) continue; q.push(nx); if(i != 0) board[nx] = board[cur] + 1; else board[nx] = board[cur]; if(nx == K){ cout << board[nx] - 1 ; return 0; } } } return 0; }
- key point!
: 현재 값의 2배로 이동하는 cost가 0이기 때문에 가중치가 제일 높아야한다. --> 가장 먼저 이동하게 dx[] 조정!
(관련 반례 : 0,2 --> 1이 나와야 함!)
Author And Source
이 문제에 관하여(BOJ : 13549 숨바꼭질3 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-13549-숨바꼭질3-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)