글 읽기 - 눈이 삔 건가 두 코드의 차이점을 못찾겠는 나.

pjkov0824 4년 전 0

두 코드의 차이점은

1. 위 코드는 통과하지 못하고 아래 코드는 통과합니다.

2. 위 코드는 if문을 인덱스를 이용해서 돌리고, 아래 코드는 값을 이용해서 돌립니다.

3. 정리하면 육안상 차이점은 하나입니다. 위 코드 36번 줄과 아래 코드 95번 줄입니다.

마가 씌였는지 뭐가 틀렸는지 모르겠습니다.

잠이 안옵니다.

여러분의 생각을 공유해주시면 감사하겠습니다.

#include <iostream>
#include <deque>

using namespace std;

int N, K;
int visit[1000001];
int ans[1000001];

int BFS()
{
    deque<int> q;
    visit[N] = 1;
    q.push_back(N);

    while (!q.empty())
    {
        int n = q.back();
        q.pop_back();

        if (n == K)
        {
            return ans[n];
        }
        

        int arr[3] = {n - 1, n + 1, 2 * n};

        for (int i = 0; i < 3; i++)
        {
            if (arr[i] >= 0 && arr[i] <= 1000000)
            {
                if (visit[arr[i]] == 0)
                {
                    visit[arr[i]] = 1;
                    if (i == 2)
                    {
                        ans[arr[i]] = ans[n];
                        q.push_back(arr[i]);
                    }else{
                        ans[arr[i]] = ans[n] + 1;
                        q.push_front(arr[i]);
                    } 
                }
            }
        }
    }
}

int main()
{
    cin >> N >> K;

    cout << BFS();
    
}

------------------------------------------------------------------------
    
#include <iostream>
#include <deque>

using namespace std;

int N, K;
int visit[1000001];
int ans[1000001];

int BFS()
{
    deque<int> q;
    visit[N] = 1;
    q.push_back(N);

    while (!q.empty())
    {
        int n = q.back();
        q.pop_back();

        if (n == K)
        {
            return ans[n];
        }
        

        int arr[3] = {n - 1, n + 1, 2 * n};

        for (int i = 0; i < 3; i++)
        {
            if (arr[i] >= 0 && arr[i] <= 1000000)
            {
                if (visit[arr[i]] == 0)
                {
                    visit[arr[i]] = 1;
                    if (arr[i] == n * 2)
                    {
                        ans[arr[i]] = ans[n];
                        q.push_back(arr[i]);
                    }else{
                        ans[arr[i]] = ans[n] + 1;
                        q.push_front(arr[i]);
                    } 
                }
            }
        }
    }
}

int main()
{
    cin >> N >> K;

    cout << BFS();
    
}

ckdgus2482 4년 전 0

위 코드가 왜 통과하는지는 모르겠지만 이 문제는 단순히 BFS로 탐색하는 문제가 아닙니다.

가중치 그래프이기 때문에 같은 노드에 도달하더라도 path에 따라서 거리가 달라질 수 있기 때문입니다.
BFS탐색으로 최단거리를 찾을 수 있는 경우는 모든 간선의 가중치가 동일한 경우입니다. 이 경우는 bfs트리의 깊이가 곧 거리이기 때문에 깊이가 낮은 것 부터 탐색하는 bfs가 최단거리를 찾을 수 있는 것입니다.

그리고 중요한건 아니지만 문제에서 노드 수는 최대 10만이라고 주어져있는데 100만으로 착각하신듯 합니다.

djm03178 4년 전 3

이 코드는 단순한 BFS가 아니라, 0-1 BFS라고 하는 알고리즘입니다. 이 문제를 푸는 데에 적합한 알고리즘입니다. 다만 코드의 로직에 약간의 결함이 있기는 합니다.

ckdgus2482 4년 전 0

그렇군요 새로운 솔루션 배워갑니다.

그래서 덱을 사용한거네요...

pjkov0824 4년 전 0

와....저런 오류가 있었군요....정말 감사합니다.

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

문제

문제

출처

ICPC

눈이 삔 건가 두 코드의 차이점을 못찾겠는 나.

pjkov0824 4년 전 0

djm03178 4년 전 1

ckdgus2482 4년 전 0

djm03178 4년 전 3

ckdgus2482 4년 전 0

pjkov0824 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말