[BOJ] 백준 16397 탈출

백준 16397 탈출

문제 링크 : https://www.acmicpc.net/problem/16397

이 문제는 갈 수 있는 모든 길을 찾아야 하는 문제 입니다.

DFS 구조로 접근할 수도 있겠지만, BFS로 하는것이 편한것 같습니다.

이 문제에서 B버튼이 눌려서 앞자리가 하나 없어졌을 경우 DFS는 정말 끝도없이 탐색만 할 것입니다. BFS 구조로 접근한다면 끝도없이 탐색하는것을 막을 수 있겠습니다.

큐에 현재 씬에서 갈 수 있는 모든 방법을 탐색하는 것 입니다.

 현재 큐에 저장되어있는 만큼만 루프를 돈다면, 몇회 돌았는지도 알 수 있습니다.

소스 코드 :

#include 
#include 
#include 
using namespace std;

int N, T, G = 0;
bool visited[100000] = { 0, };
queue q;

int main() {
 cin >> N >> T >> G;
 if (N < 0) { cout << "ANG" << endl; return 0; }
 if (T < 1) { cout << "ANG" << endl; return 0; }
 if (G < 0) { cout << "ANG" << endl; return 0; }
 
 q.push(N);
 visited[N] = true;
 // 버튼 몇개 눌렀는지 저장 변수
 int t_c = 0;
 T++;
 while (T--) {
 
  int size = q.size();
  // 큐의 크기만큼 반복
  while (size--) {
   int pos = q.front();
   q.pop();
   // 큐 맨앞과 G가 같으면 종료
   if (pos == G) { std::cout << t_c << endl; return 0; }
   // A버튼 눌렀을 경우
   if (!visited[pos + 1]) {
    q.push(pos + 1);
    visited[pos + 1] = true;
   }
   // B버튼 눌렀을 경우
   if (pos != 0) {// pos 가 0일 땐 계산 안하고 그냥 push
    int nextPos = pos * 2;
    if (nextPos < 100000) {
     int index = 0;
                    // 앞자리 하나 주는것을 구현
     for (int i = 0; i < 5; i++) {
      int divider = pow(10.0, i);
      if (nextPos / divider < 10 && nextPos / divider >= 1) {
       index = i;
       break;
      }
     }
     pos = nextPos - pow(10.0, index);

    }       
   }
   if (!visited[pos]) {
    q.push(pos);
    visited[pos] = true; 
   }
  }
  t_c++;
 }
 std::cout << "ANG" << endl;
}