[백준] 16397번 탈출

 

[적용한 알고리즘]

BFS

 

[아이디어]

숨바꼭질이랑 냄새가 비슷하다.

그냥 전형적인 BFS로 보인다. 

 

[생각의 흐름 / 절차] 

가능한 경우를 큐에 넣어주고, BFS를 실시한다. 

 

[교훈]

앞서서 4번 정도 틀렸는데, 

dist[goal] = 0 이거나 dist[goal] > t 이면 ANG을 출력하도록 했는데, 

이게 계속 50% 쯤에서 틀렸다고 나오길래 끝내 이유는 찾지 못했다. 

누군가가 알려줬으면 좋겠다.

 

그래서 bfs를 다 돌리고 정답을 리턴하게끔, 안되면 -1을 리턴하게끔 코드를 수정해줬더니

귀신같이 맞았습니다가 나왔다. 코드의 논리가 맞아도 디테일함이 중요해보인다.

 

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX 200000
using namespace std;

queue<int> q;
bool visited[MAX];
int dist[MAX];
int n, goal, t;

int getDigit(int n){
    int digit = 1;
    while (n){
        n /= 10;
        digit *= 10;
    }
    return digit / 10;
}

int bfs(){
    while (!q.empty()){
        int cur = q.front();
        q.pop();

        if (dist[cur] > t) return -1;

        if (cur == goal) return dist[cur];

        int nxt_A = cur + 1;

        if (!visited[nxt_A] && nxt_A <= 99999){
            visited[nxt_A] = true;
            q.push(nxt_A);
            dist[nxt_A] = dist[cur] + 1;
        }

        int temp = cur * 2;
        if (temp > 99999) continue;

        int nxt_B = temp;
        nxt_B -= getDigit(temp);

        if (!visited[nxt_B] && cur * 2 <= 99999){
            visited[nxt_B] = true;
            q.push(nxt_B);
            dist[nxt_B] = dist[cur] + 1;
        }
    }
    return -1;
}

int main(){
    scanf("%d %d %d", &n, &t, &goal);
    q.push(n);
    visited[n] = true;
    int result = bfs();

    if (result == -1){
        printf("ANG\n");
        return 0;
    }
    printf("%d\n", result);

    return 0;
}