글 읽기 - c++) 도움 주시면 감사하겠습니다!

dudrb0139 4년 전 0

틀렸다고 뜹니다...ㅠㅠ

bfs로 풀었습니다.

#include<iostream>
#include<deque>

using namespace std;

int check[200001] = {0,};

int main(){
    int n,k;
    cin >> n >> k;

    deque<int> seeker;
    seeker.push_back(n);
    check[n] = 0;
    while(!seeker.empty()){
        int s = seeker.front();
        seeker.pop_front();
        if(s*2 <= 200000 && check[s*2] == 0){
            check[s*2] = check[s] + 1;
            seeker.push_back(s*2);
        }
        if(s+1 <= 200000 && check[s+1] == 0){
            check[s+1] = check[s] + 1;
            seeker.push_back(s+1);
        }
        if(s-1 >= 0 && check[s-1] == 0){
            check[s-1] = check[s] + 1;
            seeker.push_back(s-1);
        }
        if(check[k] != 0){break;}
    }

    if(n==k){
        cout << 0;
    }
    else{
        cout << check[k];
    }

    return 0;
}

love94610 4년 전 1

현재 코드는 가장 빠른 시간을 찾지 않는 것 같아요

dudrb0139 4년 전 0

bfs 탐색이기 때문에 다음 탐색 지점이 0이 아니라면 탐색하는 의미가 없지 않나요??

저는 그렇게 생각하고 풀었습니다!

dudrb0139 4년 전 0

이렇게 돌리니까 맞네요...?

저는 위의 코드에서 check 리스트가 값 저장과 방문 유무(0 or not)를 저장하는 기능을 한다고 생각하고 짰는데

아래 코드처럼 ckeck와 값을 저장하는 d 리스트를 따로 두고 코드를 짜니 맞았습니다...

무슨 차이가 있는건가요??

#include<iostream>
#include<deque>

using namespace std;

bool check[200001] = {false,};
int d[200001] = {0,};

int main(){
    int n,k;
    cin >> n >> k;

    deque<int> seeker;
    seeker.push_back(n);
    check[n] = true;
    d[n] = 0;
    while(!seeker.empty()){
        int s = seeker.front();
        seeker.pop_front();
        if(s*2 <= 200000 && check[s*2] == false){
            d[s*2] = d[s] + 1;
            check[s*2] = true;
            seeker.push_back(s*2);
        }

        if(s+1 <= 200000 && check[s+1] == false){
            d[s+1] = d[s] + 1;
            check[s+1] = true;
            seeker.push_back(s+1);
        }

        if(s-1 >= 0 && check[s-1] == false){
            d[s-1] = d[s] + 1;
            check[s-1] = true;
            seeker.push_back(s-1);
        }

        if(check[k] == true){break;}
    }

    if(n==k){
        cout << 0;
    }
    else{
        cout << d[k];
    }

    return 0;
}

love94610 4년 전 0

아 제가 착각했네요 위아래 코드 차이는 n=k 일 때가 잘 처리되서 그런거 아닐까요?

dudrb0139 4년 전 0

으흠... 저도 n=k일때 2가 나올거라 생각해서 아래와 같이 처리해서 큰 문제가 없을것 같아요!

아마 계산 과정에서 제가 모르는 무언가가 있나봅니다... 아직 멀었네요ㅠㅠ

if(n==k){
    cout << 0;
}
else{
    cout << d[k];
}

seico75 4년 전 1

0 1

check[N] = 0 이 되어서 시작점인지 안가본점인지 구분이 되지 않아서 인데..

N = 0 이 아니면 이래저래 무시되는데, N = 0 이면 2 * N 도 0 이되면서 문제가 생기네요.

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

문제

문제

출처

ICPC

c++) 도움 주시면 감사하겠습니다!

dudrb0139 4년 전 0

love94610 4년 전 1

dudrb0139 4년 전 0

dudrb0139 4년 전 0

love94610 4년 전 0

dudrb0139 4년 전 0

seico75 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말