Machineboy空
17071: 숨바꼭질 5 본문
https://www.acmicpc.net/problem/17071
문제요약
1칸 좌우 이동, 2배 이동이 가능하고, 도착점도 가속 이동을 할 때, 둘이 만나는 최소 시간
난이도
Platinum 5
풀이 포인트
- 방문배열, 짝홀을 나눠 생각하는 것
- 수빈이가 동생보다 먼저 갔던 위치고, 두 번만에 이동이 가능하다면
- 아니면 한번에 만나거나!
REVIEW
어렵다 했더니 과연 플래티넘.
동생위치를 추적하고, bfs를 돌려가며 같은 경우만 생각하려 했는데,
또 짝수번째나 홀수번째의 방문배열을 따로 생각한다는 건 생각치 못했다.
손으로 예제를 풀어가니 좀 감은 오긴 했는데 두 세번은 더 봐야 이해가 갈 것 같다..
CODE
#include<bits/stdc++.h>
using namespace std;
// 같이 만나는 경우
// 먼저 도착했는데 홀짝이 맞을 경우?
const int max_n = 500000;
//[수빈위치][동생위치]
int visited[2][max_n+4]; //왜 2차원으로 만들었냐면 홀짝 따로 체크하기 위해서
int a,b, ok, turn = 1; //ok는 만났는지 체크하는 변수
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> a >> b;
if(a==b){cout << 0 << "\n"; return 0;}
queue<int> q;
visited[0][a] = 1;
q.push(a);
//cout << "수빈이의 처음 위치는 " << a <<"이고 방문배열을 1로 바꾸고, 큐에도 넣었다\n";
while(q.size()){
b += turn;
//cout << "현재 동생의 위치는 " << b << '\n';
if(b > max_n)break;
//동생 위치를 먼저 방문했다면
if(visited[turn %2][b]){
//cout << "현재 " << turn%2 << "같은 홀짝에 수빈이가 먼저 방문한 적있으므로 " << b << "위치의 동생과 만난다!";
ok = true;
break;
}
//flood fill: 단계별로 색을 칠하는 과정
int qSize = q.size();
//cout << "현재 큐 사이즈는 "<< qSize << '\n';
for(int i = 0; i < qSize; i++){
int x = q.front(); q.pop();
for(int nx: {x+1, x-1, x*2}){
//오버플로 체크,
if(nx < 0 || nx > max_n || visited[turn % 2][nx]) continue;
//cout << "수빈이의 다음 위치는" << nx <<'\n';
visited[turn % 2][nx] = visited[(turn +1)%2][x]+1;
// 동생이 와있다면 break?
if(nx == b){
//cout << nx <<"에서 동생과 만났다!\n";
ok = 1; break;
}
q.push(nx);
}
if(ok) break;
}
if(ok) break;
turn++;
}
if(ok) cout << turn << "\n";
else cout << -1 << "\n";
return 0;
}
'Computer > Coding Test' 카테고리의 다른 글
14620 : 꽃길 - dfs (0) | 2024.03.28 |
---|---|
1189: 컴백홈 - DFS (0) | 2024.03.22 |
13913 숨바꼭질 4 : bfs (1) | 2024.03.18 |
12851 : 숨바꼭질 2 - BFS (1) | 2024.02.29 |
15537 : 괄호 추가하기 - 재귀 (1) | 2024.02.28 |