[BOJ] 12851 - 숨바꼭질

https://www.acmicpc.net/problem/12851

BOJ - 숨바꼭질

문제 유형: BFS, 최단 경로

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 512MB

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다

 

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

풀이

모든 이동의 걸리는 시간이 1초라면, bfs로 최초에 만나는 턴에 종료하면 된다.

visited[i]에는 i번째 숫자에 방문하는 최소 시간의 방법의 수를 저장하고,

first_visited[i]에는 i번째에 방문하는 최소의 시간을 저장한다.

 

처음에 visited[n]에 1을, first_visited[n]에는 0을 저장한다.

steps변수로 이동시간을 계산하면서, 한 번의 steps씩 다음과 같이 bfs한다:

 현재 수의 다음수 들별로, 다음을 시행한다: (즉, 현재수-1, 현재수+1, 현재수*2)

  만약 방문한적 없다면, first_visited에 현재 steps를 저장하고, visited[다음수] = visited[현재수]를 저장한다. 그러고 큐에 다음수를 넣는다.

  만약 이번 step에서 방문한 적 있다면, visited[다음수] += visited[현재수]로, 방법의 수를 누적만 한다. 큐에는 넣지 않는다. 이미 큐에 넣어져있기 떄문이다.

 

만약 first_visited[k]에 방문처리 되어있다면, bfs를 멈추고, 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>
#define LIMIT 100001

using namespace std;

int n, k;

int first_visited[LIMIT]; // first visited step
int visited[LIMIT];       // vc[node] = count;

int main(int argc, char *argv[]) {
  for (int i = 0; i < LIMIT; ++i) {
    first_visited[i] = INT_MAX;
    visited[i] = 0;
  }
  cin >> n >> k;

  if (n == k) {
    cout << "0\n1\n";
    return 0;
  }

  first_visited[n] = 0;
  visited[n] = 1;
  int steps = 0;
  queue<int> q;
  q.push(n);
  while (!q.empty()) {
    steps++;
    int qSize = q.size();
    for (int i = 0; i < qSize; ++i) {
      int curr = q.front();
      q.pop();

      for (int next : {curr - 1, curr + 1, curr * 2}) {
        if (next >= 0 && next < LIMIT) {
          if (first_visited[next] == INT_MAX) {
            first_visited[next] = steps;
            visited[next] = visited[curr];
            q.push(next);
          } else if (first_visited[next] == steps) {
            visited[next] += visited[curr];
          }
        }
      }
    }
    if (first_visited[k] != INT_MAX)
      break;
  }

  cout << first_visited[k] << "\n";
  cout << visited[k] << "\n";

  return 0;
}