[백준] No.12851 - 숨바꼭질 2 (C++, BFS)

문제

 

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

12851번: 숨바꼭질 2

 

풀이

 

solved.ac 난이도: Gold 5

 

이전 문제인 [백준] 숨바꼭질(1697)의 다음 단계 문제입니다.

 

이전 문제는 단순히 BFS를 적용하면 풀 수 있었지만 이번에는 최단 시간으로 도달하는 방법 수 까지 구해야합니다.

각 위치의 최단 시간은 수빈이의 시작 위치로 부터 BFS를 하여 도달할 때의 탐색 깊이를 의미합니다.

 

만약 해당 위치로의 경로가 여러개가 있다면 여러개의 경로가 모두 해당 위치에 같은 최단 시간으로 도달 할 것 입니다.

즉, 이전 위치에 해당 위치로 도달할때 이전 위치들은 같은 깊이(최단 시간)를 가지는 노드들 입니다.

이때 이전 위치들도 여러개의 경로들을 가질 수 있으므로 해당 위치의 경로에 이전 노드의 경로 수를 더해 줍니다.

 

만약 해당 노드가 이미 방문되었고, 해당 노드로 최단 시간에도 도착하지 못 했다면 의미없는 경로이므로 계산할 필요가 없습니다.

 

pair<int,int> BFS(int start_pos, int dest_pos){
  queue<int> que;
  que.push(start_pos);
  time_cache[start_pos] = 0;
  case_cache[start_pos] = 1;
 
  int pos,next_pos, time,case_num;
  while(!que.empty()){
    pos = que.front();
    que.pop();
    time = time_cache[pos];
    case_num = case_cache[pos];
 
    if(pos == dest_pos)
      break;
 
    for(int i=0; i<3 ; ++i){
      switch(i){
        case 0:
          next_pos = pos -1;
          break;
        case 1:
          next_pos = pos +1;
          break;
        case 2:
          next_pos = pos*2;
      }
 
      if(next_pos < 0 || MAXN < next_pos )  //범위 초과 판단
        continue;
      
      if(time_cache[next_pos] == -1){//방문한적 없는 경우
        que.push(next_pos);
        time_cache[next_pos] = time +1;
        case_cache[next_pos] = case_num;
      }else if(time_cache[next_pos] == time +1){  //최단 시간에 도달하는 경로가 여러가지인 경우
        case_cache[next_pos] += case_num;
      }
 
    }// for문 end;
 
  }
 
  return make_pair(time_cache[dest_pos], case_cache[dest_pos]);
}

 

 

 

코드