[백준] 1697번: 숨바꼭질 (C++ 풀이)

문제

풀이1(DP)

나는 처음에 이 문제를 dp로 풀 수 있을 거라고 생각했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
 
int n, k;
int d[100001];
 
int main() {
    scanf("%d %d", &n, &k);
 
    //동생<수빈 일경우 갈수있는 방법이 무조건 '현재-1'일거라 생각
    if (n > k) { 
        printf("%d\n", n - k);
        return 0;
    }
    
    d[n] = 0;    //시작은 0초
    //초기화 부분
    if (n == 0)
        d[n + 1] = 1;    //음수는 생각하지 않음
    else
        d[n - 1] = d[n + 1] = 1;
 
    //n k가 5 17이라 하면 (i:7~18)
    for (int i = n + 2; i <= k + 1; i++) {
        //i가 짝수일경우 min(x+1걷기, 순간이동)
        if (i % 2 == 0)
            d[i] = min(d[i - 1] + 1, d[i / 2] + 1);
        else    //홀수일경우 x+1걷기
            d[i] = d[i - 1] + 1;
 
        //d[i]를 채운이후 d[i-1]의 값 갱신->x-1걷기가 최소인지 확인해서 갱신
        d[i - 1] = min(d[i - 1], d[i] + 1);
    }
 
    printf("%d\n", d[k]);
 
    return 0;
}

그래서 이런 식으로 짰었는데 n k 가 8 10일때 d[i/2]+1 하는 부분을 처리해줘야 하는 등 여러 예외처리를 더 해줘야하는 복잡함이 있었다.

dp로 풀 수 있을 거라 생각했는데 내가 아직 모자라서 어디서부터 어떻게 틀린것인지 찾을 수 없어 관두고 bfs로 풀기로 했다.

 

depth를 수빈이가 동생을 찾는 시간(초)라고 생각했다. 그래서 dfs보다는 넓이 우선 탐색인 bfs가 적당하겠다고 생각했다.

갔던 숫자를 다시 갈 필요가 없어서 visited배열을 선언했고,

방문하지 않았으면 0, 방문을 했으면 depth값을 저장했다.

 

그리고 뒤로 간 값이 0이상, 앞으로 간 값은 100,000이하로 경계값처리 해주면서 방문했다.

 

나중에 다시 한번 풀어봐야겠다

 

 

+ db 풀이법 해결!!

 

n-1부터 table을 채웠던 것이 문제였따

n-1이하의 table을 채웠더니 통과했다

질문에 답해주신 분께 너무 감사하다ㅠㅠ

 

int idx = n - 2, tmp = 2;
    while (idx >= 0) {
        d[idx] = tmp;
        idx--;
        tmp++;
    }

 

이렇게 n-1이하의 값을 초기화해주었더니 해결되었따

코드1

풀이2(BFS)

BFS로 풀어보았다.

큐에 방문 정점을 저장하고, vis배열에 이미 방문한 배열을 체크해주었다.

한 정점에 대해 x-1, x+1, 2x 트리 형식으로 쭉쭉 나가는 형식으로 진행하였고

vis배열에는 이에 대한 트리의 레벨을 저장했다. 트리의 레벨이 즉, 동생을 잡는 시간이다.

 

코드2

결과