[백준 1753] 잘못된 다익스트라 코드

November 29, 2020

1. 글을 쓰게 된 이유

2020 KCPC를 준비하면서 다익스트라 코드를 연습하고자 백준 9370 문제를 풀어보았다.
문제는 내가 생각한 풀이 방법이 옳은 정답이었는데도 계속 틀린 코드가 나왔던 것
BAPC 문제였기 때문에 테스트 케이스를 홈페이지에서 구할 수 있었고, 코드를 수정해나가는 도중 이상한 TC를 발견하게 됨
이 TC를 통해 사실은 그동안 내가 짜왔던 다익스트라 코드가 최단 경로를 제대로 발견하지 못하는 틀린 코드였다더라 그런 이야기!

2-1. 원래 코드

내가 풀었던 백준 1753 소스코드를 수정한 것
수정 사항
- 전체출력 대신 d[238]만 출력하도록 변경
- P[] 벡터의 자료형을 vector<pair<int,char>> 에서 vector<pair<int,int>>로 변경
- 단방향 edge였던것을 양방향 edge로 변경

#include <stdio.h>
#include <queue>
#define MaxNum 20001
#define INF 9999999
#define white 0
#define gray 1
#define black 2
using namespace std;
int d[MaxNum];
vector<pair<int, int>> P[MaxNum];
char visit[MaxNum];
typedef struct compare
{
    bool operator()(int i, int j)
    {
        return d[i] > d[j];
    }
} cmp;

priority_queue<int, vector<int>, cmp> pq;
int V = 0, E = 0, s = 0;
void Dijkstra(int s);
int MIN(int a, int b);

int main()
{
    // init
    for (int i = 0; i < MaxNum; i++)
    {
        d[i] = INF;
        visit[i] = white;
    }

    scanf("%d %d", &V, &E);
    scanf("%d", &s);

    // edge의 값들을 입력한다
    for (int e = 0; e < E; e++)
    {
        int x = 0, y = 0, d = 0;
        scanf("%d %d %d", &x, &y, &d);
        P[x].push_back(pair<int, int>(y, d));
        P[y].push_back(pair<int, int>(x, d));
    }
    Dijkstra(s);

    // 결과 출력

    printf("%d", d[238]);
}

int MIN(int a, int b)
{
    if (a > b)
        return b;
    else
        return a;
}
void Dijkstra(int s)
{
    // s = starting vertex
    visit[s] = gray;
    d[s] = 0;
    pq.push(s);
    while (!pq.empty())
    {
        // pop
        int x = pq.top();
        pq.pop();
        // 이미 방문한 노드는 건너뛴다
        if (visit[x] == black)
            continue;
        // process : 인접노드들의 최단 경로를 업데이트한다.
        for (int y = 0; y < P[x].size(); y++)
        {
            int dest = P[x][y].first;
            if (visit[dest] != black)
            {
                d[dest] = MIN(d[dest], d[x] + P[x][y].second);
                // 경로가 업데이트된 노드들은 큐에 넣어준다.
                pq.push(dest);
                visit[dest] = gray;
            }
        }
        // 방문 처리
        visit[x] = black;

    }
}

2-2. 원래 코드의 문제점

내가 원래 짰던 코드는 다음과 같이 우선순위큐가 ‘최단거리 저장 배열’에 직접 접근해서 (이 코드에서는 d[])
이 최단거리를 기준으로 Sorting을 수행했었다

typedef struct compare
{
    bool operator()(int i, int j)
    {
        return d[i] > d[j];
    }
} cmp;

이 코드대로 아래 TC를 수행하면 d[238]의 값이 1026으로 출력된다
정답은 965

TC 보기

3. 문제점 수정

기존방법 :
- priroriy queue에는 단순히 노드 번호만 삽입
- 정렬 시에는 직접 d[]배열에 접근하여, 이 정보를 기준으로 정렬
새 방법 :
- priority queue에 (노드, 거리) 쌍을 삽입
- 정렬시에는 (노드, 거리) 안의 두번째 인자 (거리 요소)를 사용하도록 수정
수정한 코드 :
- compare 함수
  - 변경 전/후 코드 비교

typedef struct compare
{
    bool operator()(int i, int j)
    {
        return d[i] > d[j];
    }
} cmp;

struct compare
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second > b.second;
    }
};

priority queue 자료형
- 변경 전 : int
- 변경 후 : pair<int,int>
전체 코드

#include <stdio.h>
#include <queue>
#define MaxNum 20001
#define INF 9999999
#define white 0
#define gray 1
#define black 2
#define pii pair<int, int>
using namespace std;
int d[MaxNum];
vector<pair<int, int>> P[MaxNum];
char visit[MaxNum];
struct compare
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second > b.second;
    }
};
priority_queue<pii, vector<pii>, compare> pq;
int V = 0, E = 0, s = 0;
void Dijkstra(int s);
int MIN(int a, int b);

int main()
{
    // init
    for (int i = 0; i < MaxNum; i++)
    {
        d[i] = INF;
        visit[i] = white;
    }

    scanf("%d %d", &V, &E);
    scanf("%d", &s);

    // edge의 값들을 입력한다
    for (int e = 0; e < E; e++)
    {
        int x = 0, y = 0, d = 0;
        scanf("%d %d %d", &x, &y, &d);
        P[x].push_back(pair<int, int>(y, d));
        P[y].push_back(pair<int, int>(x, d));
    }
    Dijkstra(s);

    // 결과 출력

    printf("%d", d[238]);
}

int MIN(int a, int b)
{
    if (a > b)
        return b;
    else
        return a;
}
void Dijkstra(int s)
{
    // s = starting vertex
    visit[s] = gray;
    d[s] = 0;
    pq.push(make_pair(s, 0));
    while (!pq.empty())
    {
        // pop
        int x = pq.top().first;
        int value = pq.top().second;
        pq.pop();
        // 이미 방문한 노드는 건너뛴다
        if (visit[x] == black)
            continue;
        // process : 인접노드들의 최단 경로를 업데이트한다.
        for (int y = 0; y < P[x].size(); y++)
        {
            int dest = P[x][y].first;
            if (visit[dest] != black)
            {
                d[dest] = MIN(d[dest], d[x] + P[x][y].second);
                // 경로가 업데이트된 노드들은 큐에 넣어준다.
                // printf("Updating Dest : %d\n", dest);
                pq.push(make_pair(dest, d[dest]));
                visit[dest] = gray;
            }
        }
        // 방문 처리
        visit[x] = black;
    }
}

이 코드 또한
- Line 46 주석 처리
- 모든 최단거리 출력 처리
하고 백준 1753에 제출하면 맞았습니다를 얻을 수 있다.

4. 깨달은 점

다익스트라를 구현할 때에는 저렇게 d[]에 직접 접근해서 priority queue를 정렬하는 방식을 쓰면 안된다
왜인지 모르지만 에러가 난다
에러가 나는 원인은 아직 잘 모르겠다
- 내 생각에는 d[] 배열 직접 접근도 문제 없는 알고리즘인 것 같은데 음
- 분석하고 싶은데 TC가 너무 길어서 분석할 엄두가 안난다
저 TC는 양방향 edge로 수정해서 1753에 데이터 추가해달라고 요청할 예정

Twitter Facebook LinkedIn

Jiwon Kang

[백준 1753] 잘못된 다익스트라 코드

1. 글을 쓰게 된 이유

2-1. 원래 코드

2-2. 원래 코드의 문제점

3. 문제점 수정

4. 깨달은 점

공유하기

참고

[백준] 1865 웜홀 : 문제의 논란 정리

[알고리즘] 트리의 지름 증명

[백준] 2206 : 벽 부수고 이동하기

코딩 테스트 대비 정리