글 읽기 - 숨바꼭질 문제.. 반례는 찾았으나

jsstar522 5년 전 1

숨바꼭질 문제

두가지 질문이 있습니다!

많은 분들이 올려놓은 소스코드를 참고해서 작성했는데 왜틀렸는지 알수가없네요 ㅠㅠ 다른 반례들을 많이 찾아서 넣어봤는데 작동은 잘하는 것 같은데요... N>K 일때, 특히 K가 1이나 0일때 출력값이 0으로 나와버리네요. 모든 경우를 Printf해서 살펴본 결과 now값이 1이나 0이 될때까지 작동을 안합니다 ㅠㅠ 도와주세요
몇몇 소스코드를 보면 now == k 와 같은 조건을 걸어서 while 문을 break 걸지 않고 모두 계산한 후 k에 해당하는 비용을 출력하는 경우가 있던데 이런경우, 두가지 이상의 경우의 수가 나올 때 출력하면 틀리지 않나요? (문제 예제의 경우처럼 5-10-9-18-17 말고도 5-6-7-...-16-17 의 경우의 비용도 데이터에 저장되지 않나요?)

#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;
 
int main()
{
    int n;    //수빈위치 입력
    int k;    //동생위치 입력
    
    scanf("%d", &n);
    scanf("%d", &k);
    
    queue<int> q;
    bool visited[100000];
    int time[100000] = {0};
    int now;
    
    visited[n] = 1;
    time[n] = 0;
    q.push(n);
    
    while(!q.empty())
    {
        now = q.front();
        q.pop();
    
        if(now == k)
        {
            break;
        
        }
        if(now-1 >= 0 && visited[now-1] == false)
        {
            q.push(now-1);
            visited[now-1] = true;    //방문하는 곳은 True 값을 부여한다.
            time[now-1] = time[now] + 1;    //이동한 경로마다 1을 쌓는다.(시간계산)
                
        }
        if(now+1 <= 100000 && visited[now+1] == false)
        {
            q.push(now+1);
            visited[now+1] = true;
            time[now+1] = time[now] + 1;
        }
        if(now*2 <= 100000 && visited[now*2] == false)
        {
            q.push(now*2);
            visited[now*2] = true;
            time[now*2] = time[now] +1;
        }
    }
    printf("%d \n", time[k]);
}

hyunynim 5년 전 1

지금 올려놓으신 코드에서 visited 배열이 정상적으로 초기화 될지가 의문입니다.

모두 false로 초기화 되기를 원하셨다면 = {0}; 을 붙여주시거나 전역변수로 선언해주시는게 좋을 듯 합니다.

뿐만아니라 수빈이와 동생이 있을수 있는 위치는 0 ~ 100000 이므로 배열의 인덱스를 100000까지 사용합니다.

따라서 배열의 크기역시 100000이 아닌 100001 이상으로 설정해줘야 합니다.

jsstar522 5년 전 0

hyunynim 님

감사합니다 ㅠㅠ

결과적으론 초기화보다 말씀해주신 배열의 크기가 문제가 됐습니다.

물론 초기화도 시켜주는 것도 중요하기 때문에 이걸 포함해서 배열의 크기도 간과했던 점에서 끙끙댔네요...ㅠㅠ

너무 감사드립니다 !!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

숨바꼭질 문제.. 반례는 찾았으나

jsstar522 5년 전 1

hyunynim 5년 전 1

jsstar522 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말