글 읽기 - 1697번 반례 질문드립니다

qqwq9999 5년 전 0

정답률 50프로 정도에서 틀렸습니다가 발생합니다..

1697번 틀렸습니다 질문글을 4페이지까지 뒤져보고 반례를 전부 적용했을 때는 답이 올바르게 나왔습니다 ㅜㅜ

제 코드의 경우 반례가 어떤게 있을까요..?

#include <iostream>
#include <stdio.h>
#include <queue>
#include <utility>

using namespace std;

int dep, dst;

bool isValidNum(int num) {
    return num >= 0 && num <= 100000;
}

void goDeparture(){
    queue <pair<int, int> > bsfList;
    bool visited[100001];
    
    visited[dep] = true;
    bsfList.push(make_pair(dep, 0));
    
    while(!bsfList.empty()) {
        int vertex = bsfList.front().first;
        int count = bsfList.front().second;
        
        bsfList.pop();
        
        if (vertex == dst) {
            cout<<count<<endl;
            return;
        }
            for(int i = 0; i<3; i+=1) {
                int nextVertex;
                switch(i){
                    case 0:
                        nextVertex = vertex - 1;
                        break;
                    case 1:
                        nextVertex = vertex + 1;
                        break;
                    case 2:
                        nextVertex = vertex * 2;
                        break;
                }
                if(isValidNum(nextVertex) && !visited[nextVertex]) {
                    bsfList.push(make_pair(nextVertex, count + 1));
                    visited[nextVertex] = true;
                }
            }
    }
}


int main(int argc, const char * argv[]) {
    
    cin>>dep>>dst;
    goDeparture();
    
    return 0;
}

greedev 5년 전 1

compile online에서 돌려봤을때

100000 0 넣으면 작동 안되던데

한번 해보시면...

djm03178 5년 전 1

visited가 초기화되지 않았습니다.

djm03178 5년 전 0

그건 dep>dst인 경우에 대한 예외 처리를 했을 뿐이고, 나머지 부분은 동작이 어떻게 될지 알 수 없습니다.

greedev 5년 전 0

50프로 정도에서 틀렸다면 초기화 문제는 아닐 것 같네요

greedev 5년 전 0

그리고 예외를 처리하니 맞았습니다...

djm03178 5년 전 1

문제가 아닐 것 같다고 하지 말고, 초기화가 되지 않았는데 동작이 잘 되느냐는 그냥 운입니다. 0이라는 값은 메모리 상에 빈도가 극도로 높으니, 운 좋게 통과되는 것도 무리가 아니죠. 똑같은 환경이라면 여러 번 반복해도 같은 결과를 낼 가능성도 매우 높습니다.

greedev 5년 전 1

아 그럴수도 있겠군요;;;

그런데 혹시 c++과 c++14 차이점 아시나요?

아래 소스는 c++14에서 돌아가는것 같긴 한데...

djm03178 5년 전 1

좀 더 확률론적인 이야기를 하자면, 작은 좌표에서 큰 좌표로 이동하는 건 대체로 적은 이동 횟수로도 도달이 가능하므로 비교적 적은 수의 좌표들의 visited만 "운 좋게 0"이었으면 됩니다. 하지만 역으로 위에서 내려올 때는 그 사이에 있는 모든 좌표를 다 방문해야 하므로 단 하나라도 0이 아닌 게 있었다면 정답을 찾을 수가 없습니다.

이 코드에서 visited만 0으로 초기화하고 시작해도 맞습니다. 굳이 예외 처리를 할 필요가 없이, 어떤 환경이라도 항상 올바른 알고리즘을 만들 수 있는데, 굳이 나머지는 운에 맡기고 특수 상화에 대한 예외 처리만 할 필요는 없죠.

greedev 5년 전 0

그렇군요...

저의 짧은 생각과는 다르게 매우 대단하십니다...센세...

qqwq9999 5년 전 0

두 분 다 답변 감사합니다. 로직에 대해 정확한 이해없이 작성하다보니 초기화도 잊었네요. 댓글 감사합니다.

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

문제

문제

출처

ICPC

1697번 반례 질문드립니다

qqwq9999 5년 전 0

greedev 5년 전 1

djm03178 5년 전 1

djm03178 5년 전 0

greedev 5년 전 0

greedev 5년 전 0

djm03178 5년 전 1

greedev 5년 전 1

djm03178 5년 전 1

greedev 5년 전 0

qqwq9999 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말