JArchive 프로그래밍 일기

문제

숨바꼭질3 백준 13549

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, k;
int vis[100005];

bool rangecheck(int x){
  return (x >=0 && x <= 100000);
}

void bfs(){

  queue<int> qu;

  vis[n] = 0; // 수빈이의 현재 위치는 0초에 도달.
  qu.push(n);

  while(!qu.empty()){
    int cx = qu.front();
    qu.pop();

    if(cx == k){
      cout << vis[cx]<< '\n';
      break;
    }

    for(auto nx : {cx*2, cx + 1, cx - 1}){

      if(!rangecheck(nx) || vis[nx] <= (vis[cx]+1)) continue;

      if((cx*2) == nx) {
        vis[nx] = vis[cx];
      }else{
        vis[nx] = vis[cx] + 1;
      }
      qu.push(nx);
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int bignum = 1e9;
  fill(vis, vis+100004, bignum);

  cin >> n >> k;

  bfs();

  return 0;
}

리뷰

다시 풀어봐야 할 문제.

내가 위치 2에 있다.
위치 2에서 '위치 4'로 이동할 때, 예전에 방문할 때 보다 '적은 시간'이 걸려야 한다.
즉, '위치 4'로 가는 시간이 2초가 걸릴 수도 있고, 0초가 걸릴 수도 있다.

현재 위치2 이고, 이동 방법은 x2 해서 순간이동 하는방법, +1또는 -1하는데 1초가 걸리는 방법이 있다.
+1 을 2번 하면 2초가 걸려서 위치 4에 도착할 수 있다.
x2를 하고 순간이동하면 0초가 걸려서 위치 4에 도착할 수 있다.

따라서 위치 배열 인덱스 4에는 '0초'가 저장되어야 한다.

'가장 빠른 시간' 을 구해야 하니까 모든 위치의 초기 시간값을 2^9 로 크게 잡아놨다.

bfs로 순회할 때, "예전에 방문할 때 보다 '적은 시간'이 걸려야 한다" 를 만족시키기 위한 조건이 필요했다.

그래서 '현재시간 +1초' 와 다음위치가 저장하고 있는 도달 시간을 비교했다. 다음위치가 저장하고 있는 도달 시간이 더 커야 이동할 수 있게 했다.

현재 위치 시간이 2초 라고 했을 때. 2초 + 1초, 즉 3초가 다음 위치에 저장할 시간이 된다.
현재까지는 2초가 걸렸고 다음 위치에는 3초가 걸릴 수 있는 방법으로 현재까지 도달해왔다는 뜻이다.

다음 위치에 이미 3초가 저장되어 있다면, 다음 위치의 시간을 더 짧게 갱신해줄 필요가 없다.
다음 위치에 만약 4초가 저장되어 있다면, 3초를 저장하려고 했으니까 갱신해주면 된다.