[C/C++] 13549: 숨바꼭질 3 (BFS,Queue)

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

13549번: 숨바꼭질 3

 

 결론부터 말하자면 이 문제는 queue를 이용해 bfs로 풀 수 있는데 이때 2의 배수일 때는 0초만에 도달 가능하다는 것만 유의하면 된다.

 

구현??

 

 이를 구현하기 위해서 내가 사용했던 방법은 함수 after_onesec와 after_zero이다. 

after_onesec는 1초뒤에 갈 수 있는 곳을 queue에 넣는 방식으로 동작되는데 이때 queue.front에서 값을 받아서 그 값보다 +1인 수와 +1인 수를 각각 변수 tmp1과 tmp2로 받은 뒤에 이 변수들이 문제 범위에 맞는지, 이 전에 지나갔는지를 확인하여 모두 만족한 경우 queue에 넣어주고 visit_once[변수]의 값을 1로 바꿔주는 역할을 한다.

 

 여기서 중요한 건 after_zero 함수인데 0초 동안은 2의 배수만큼 범위내에서 무한히 갈 수 있으므로 after_zero를 실행한 뒤에 모든 가능한 수를  queue에 넣고 1초가 지난 뒤에 갈 수 있는 곳을 after_onesec 함수에서 처리하도록 구현하였다.,

 여기서 가장 핵심적인 것은 queue.front의 값을 다시 queue의 넣어주고 queue.front 값은 pop시키는 것인데 가장 front의 값도 1초뒤에 어떻게 될지 모르기 때문에 저장해줘야 함이다. 

 

 C++에서 내장함수 queue를 이용할 때 매우 단순한 함수이므로 queue에 임의의 원소에 접근할 수 없다. 오직 front와 back에만 접근이 가능하기 때문에 이렇게 비효율적으로 보이는 듯한 과정을 코드에 넣은 것이다. 다른 방법으로 풀면 더 간단하게 풀 수도 있다.

 여기에 queue.front 값을 while 문을 통해 2의 배수씩 시켜 범위의 들어간다면 queue에 넣어주고 답을 찾으면 return 하도록 만들었다.

 

주의해야할 점?

 위에서 언급한 것 이외에도 주의해야 할 점들이 있다

 

1. visit 배열의 범위

  visit 배열의 초기화를 200,000이상으로 할 경우 메모리 초과가 나올 수도 있으니 100,000이 넘으면 queue에 저장하지 못하도록 하는 조건문을 추가하여 이를 막아야한다. 또한 visit 배열을 통해 이미 지나간 점을 다시 가지 않게 만들어야만 queue의 size가 100,000 이하로 나오면서 시간 제한과 메모리 제한을 극복할 수 있다

 

 

2. 문제를 잘 읽자

 사실 증명은 하지 않겠지만 수빈이가 100,000보다 큰 곳으로 가는 경우는 없다. 가장 대표적인 예로 50001과 100000이 있는데 50001->100002->100001->100000 (ans:3) 보다 50001->50000->100000 (ans:1)이 더 빠른 시간내에 도착할 수 있는 경우이다. 

 

반례?

//4 6: 1

//1 10000: 3      1 100000 : 5
//7 100000: 5    8 100000:6   9 100000: 7

 

소스코드

 

#include <iostream>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<set>
using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

queue<pair<int,int>> q1;
vector<int>visit_once(100002);

int after_onesec(int day,int ans) //queue에서 하나를 꺼내고 똑같은거 다시함!
{
  int size=q1.size();
  for(int i=0;i<size;i++)
    {     
      int tmp1=q1.front().first-1;
      int tmp2=q1.front().first+1;
      if(tmp1==ans || tmp2==ans)
        return 2;

      if(tmp1>=0 && visit_once[tmp1]==0){
        q1.push(make_pair(tmp1,day));
        visit_once[tmp1]=1;
      }
      
      if(tmp2<=100000 && visit_once[tmp2]==0)
      {
        q1.push(make_pair(tmp2,day));
        visit_once[tmp2]=1;
      }          
      q1.pop();
      
    }
    
  return 0;
}

int after_zero(int day,int ans)
{
  int size=q1.size();
  for(int i=0;i<size;i++)
    {
      int tmp=q1.front().first; // 맨 앞에 있는 수를 다시 queue에 넣고 맨 앞에 있는 수는 삭제
      q1.push(make_pair(tmp,day));
      visit_once[tmp]=1;
      q1.pop();
      
      while(tmp<=2*ans &&tmp<=100000){       
        if(tmp==ans) //찾았다        
          return 1;
        if(tmp==0)
          break;
        
        if(visit_once[tmp]==0 &&tmp<100001){ //아직 지나간 곳이 아니다!
          q1.push(make_pair(tmp,day));
          visit_once[tmp]=1;
        }        
        tmp*=2;
    }
            
  }
  return 0;
}

int main() {    
  int n,ans;
  cin>>n>>ans;
  int tmp=n,day=0;
  int find_answer=0;
  q1.push(make_pair(n,0));
  visit_once[n]=1;
  
  while(1)
    {
      find_answer=after_zero(day,ans);     //1을 return 
      if(find_answer==1)
        break;
      day++;
      find_answer=after_onesec(day,ans); //2를 return
      if(find_answer==2)
        break;

      
    }
  
    cout<<day;
 // cout<<q1.back().second;
  
}
//1 10000: 3      1 100000 : 5
//7 100000: 5    8 100000:6   9 100000: 7