[백준 13549] 숨바꼭질3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

단순 bfs로 접근했다가 틀렸다.

단순 bfs로 접근하면 안되는 이유는 순간이동시에 2*x를 이동하지만 0초가 걸리기 때문이다. 현재 노드에서 아래 레벨로 접근하는게 아니라 같은 레벨 상에 노드가 하나 더 생기는 셈이다.

 

사용하는 알고리즘 0-1 bfs

0-1 bfs란 그래프에 가중치가 0과 1로 구성된 경우 사용하는 bfs이다. 여기서 가중치란 노드의 레벨로 보면 될 것 같다.

일반 bfs는 가중치가 모두 동일하다. 

 

0-1 bfs를 사용하기 위해 앞뒤로 넣고 뺄 수 있는 덱을 사용한다.

순간이동을 할 경우엔 0초가 소요되므로 push_front를 나머지 경우엔 1초가 소요되므로 push_back을 한다.

 

++ 처음에 런타임에러가 나왔는데 fr의 범위 때문이었다. 

if (fr + 1 < MAX && !visited[fr + 1]) 의 순서를 if (!visited[fr + 1] && fr + 1 < MAX )로 바꾸면 런타임에러가 난다. 앞에서부터 조건을 체크하기 때문에 visited[fr+1]이 범위를 벗어난 순간 오버플로우가 발생한다. 주의하자

 

#include <stdio.h>
#include <string.h>
#include <deque>
#define MAX 100001

using namespace std;

int n, k;

int visited[MAX];
int main(void)
{
  scanf("%d %d", &n, &k);
  memset(visited, 0, sizeof(visited));
  deque<int> dq;
  dq.push_front(n);
  visited[n] = 1;

  while (!dq.empty())
  {
    int fr = dq.front();

    if (fr == k)
    {
      printf("%d\n", visited[k] - 1);
      return 0;
    }

    dq.pop_front();

    if (fr * 2 < MAX && !visited[fr * 2])
    {
      dq.push_front(fr * 2);
      visited[fr * 2] = visited[fr];
    }

    if (fr > 0 && !visited[fr - 1])
    {
      dq.push_back(fr - 1);
      visited[fr - 1] = visited[fr] + 1;
    }

    if (fr + 1 < MAX && !visited[fr + 1])
    {
      dq.push_back(fr + 1);
      visited[fr + 1] = visited[fr] + 1;
    }
  }
  return 0;
}