Computer Science & Engineering

https://www.acmicpc.net/problem/1260

이 문제는 비 방향성 그래프의 간선이 주어졌을 때 V번 정점부터 시작하여 DFS로 탐색한 결과와 BFS로 탐색한 결과를 각각 출력하는 기본적인 그래프 탐색 문제이다. 입력은 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V와 M개의 간선들로 이루어진다. 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MN = 1001;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문 여부
void dfs(int N) { //DFS
    vst[N] = true; //방문 체크
    cout << N << ' '; //방문한 노드 번호 출력
    for(int e : g[N]) { //방문한 노드로부터 인접 리스트를 확인
        if(!vst[e]) dfs(e); //방문하지 않은 노드 방문
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, V; cin >> N >> M >> V;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //인접리스트 추가
        g[v].push_back(u);
    }
    for(int i = 1; i <= N; i++) { //정점 번호 오름차순으로 정렬
        sort(g[i].begin(), g[i].end());
    }
    dfs(V); //V번 정점부터 DFS
    cout << "\n" << V; //DFS출력 마지막을 나타내는 개행 후 BFS 시작정점 V출력
    queue<int> q; //BFS에 사용할 queue
    memset(vst, 0, sizeof(vst)); //방문 배열 초기화
    q.push(V); //시작 정점 queue에 추가
    vst[V] = true; //시작 정점 방문 체크
    while(!q.empty()) { //모든 정점을 방문할 때까지
        int now = q.front(); q.pop(); //queue의 첫 번째 pop
        for(int e : g[now]) { //인접리스트 확인
            if(!vst[e]) { //방문하지 않은 노드 발견할 경우
                cout << ' ' << e; //정점 출력
                vst[e] = 1; //방문 체크
                q.push(e); //queue에 추가
            }
        }
    }
}

방문하는 정점은 번호가 작은 것부터 우선적으로 방문해야하므로 우선 각 정점의 인접리스트를 오름차순으로 정렬한다.

    DFS를 우선적으로 출력하기 때문에 방문하지 않은 노드를 발견할 경우 곧바로 DFS로 탐색하여 정점을 출력하고 방문체크를 한다. 그 다음 그 노드로부터 인접리스트를 확인하여 더 탐색할 수 있는 정점이 있는지 확인한다. 있을 경우 재귀적으로 탐색한다.

    BFS는 queue를 이용한다. 방문한 노드를 체크하고 큐에 넣는다. 큐는 FIFO(First In First Out)이기 때문에 방문한 노드를 순서대로 확인할 수 있다. 시작정점 V를 큐에 넣고 방문 체크를 한다. 반복문은 큐가 빌때까지 반복한다. 큐의 첫 번째 원소를 pop한 후 그 원소의 인접 리스트를 확인한다. 방문하지 않은 노드를 발견할 경우 그 정점을 출력하고 방문체크를하고 큐에 push한다.

    백준에서는 개행이나 공백이 한 두개 더 출력되더라도 오답처리를 하지 않기 때문에 마지막일 경우 뒤에 공백이나 개행을 넣지 않기 위한 예외를 처리하지 않아도 된다.

https://www.acmicpc.net/problem/4963

이 문제는 BFS와 DFS 모두 풀 수 있는 문제이다. 글쓴이는 DFS를 이용하여 이 문제를 풀어보았다. 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stdbool.h>
#include <vector>
#include <cstring>

using namespace std;

const int MN = 51;

int map[MN][MN]; //인접행렬
bool vst[MN][MN]; //방문 여부
int di[8] = {1, 0, 0, -1, 1, -1, 1, -1}; //8가지 방향으로 이동을 나타냄
int dj[8] = {0, 1, -1, 0, 1, 1, -1, -1};
int w, h;
void dfs(int i, int j) {
    vst[i][j] = true; //방문 체크
    for(int d = 0; d < 8; d++) { //8가지 방향을 탐색
        int ni = i + di[d]; //다음 i좌표
        int nj = j + dj[d]; //다음 j좌표
        if(0 <= ni && ni < h && 0 <= nj && nj < w) { //지도를 벗어나는지 확인
            if(!vst[ni][nj] && map[ni][nj]) { //방문 여부와 땅인지 여부 확인
                dfs(ni, nj); //재귀로 DFS 탐색
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    while(true) { //0을 입력받을 때까지 반복
        cin >> w >> h;
        if(w == 0 && h == 0) break; //0이 두 개 입력될 경우 종료
        memset(map, 0, sizeof(map)); //테스트케이스마다 초기화
        memset(vst, 0, sizeof(vst)); //테스트케이스마다 초기화
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                cin >> map[i][j]; //지도 입력
            }
        }
        int cnt = 0;
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(map[i][j] && !vst[i][j]) { //땅이고 방문하지 않은 경우 DFS 탐색
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }
}

이 문제는 지도를 주어졌을 때 상하좌우 대각선으로 땅이 이어져 있다고 할 때 분리된 섬의 개수를 구하는 문제이다. 우리는 x, y좌표 형식으로 문제를 입력받기 때문에 위 코드의 di, dj 배열과 같이 8가지 방향을 나타낼 수 있다. 그림으로 나타내면 다음과 같이 나타낼 수 있다.

i, j에서 8가지 방향의 좌표를 더해 ni, nj 좌표를 구한다. 이때 지도를 벗어나는지를 확인해준다. 그렇지 않으면 Out of Bounds 에러가 발생할 수 있다.  그 다음 방문 여부와 땅인지의 여부를 확인하여 DFS 탐색을 계속한다. 이때 지도에서 땅인 부분의 DFS 횟수가 곧 섬의 개수인 것을 알 수 있다. 이전에 풀은 연결 요소의 개수와 구하는 방식이 비슷한 것을 알 수 있다. 차이점은 인접리스트 형식이 아니라 좌표형식으로 주어진 입력을 활용하여 좌표를 이동하며 DFS를 한다는 것이다.

https://www.acmicpc.net/problem/11724

이 문제는 방향이 없는 그래프를 주어졌을 때, 연결 요소의 개수를 구하는 문제이다. 즉 간선으로 연결되어 있는 집합의 개수가 총 몇 개인지를 출력하는 프로그램이다. bfs, dfs 모두 사용할 수 있는 문제지만 나는 dfs를 이용하였다. 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

bool visit[1001]; //방문 여부 판단
vector<int> g[1001]; //인접 리스트
void dfs(int n) { //DFS 함수
    visit[n] = 1;
    for(int nxt : g[n]) {
        if(!visit[nxt])
            dfs(nxt);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); //시간 감소
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //비방향성 그래프이므로 인접 리스트에 u->v, v->u 모두 추가
        g[v].push_back(u);
    }
    int cnt = 0;
    for(int i = 1; i <= N; i++) { //1부터 N까지 dfs를 하며 연결 요소의 개수 카운트
        if(!visit[i]) { //방문하지 않은 번호에서만 dfs
            dfs(i);
            cnt++;
        }
    }
    cout << cnt;
}

이 문제는 가장 간단한 DFS 문제중 하나이다. 1번 노드부터 N번 노드까지 DFS를 이용해 전부 방문하고 나면 visit 배열을 통해 방문한 노드인지 확인할 수 있다. 그러므로 이미 방문한 DFS의 횟수를 통해 연결 요소의 개수를 셀 수 있다.

인접 행렬은 인접 리스트에 비해 많은 메모리를 소모하기 때문에 vector를 지원하는 C++에서는 인접 리스트를 사용하는 것이 굉장히 좋다. DFS에서 재귀를 이용해 탐색할 때 방문 여부를 언제 체크하냐에 따라 재귀의 횟수를 많이 줄일 수 있다. 위와 같이 재귀를 하기 전에 방문 여부를 확인할 경우가 있고 재귀를 들어가서 첫 줄에 방문했을 경우 return하는 방식으로 프로그램을 구현할 수 있다. 후자의 경우 불필요한 방문이 될 수 있으므로 위의 코드와 같이 전자 방식으로 구현하는 것이 더 효율적이다.

https://programmers.co.kr/learn/courses/30/lessons/42579

이 문제는 프로그래머스의 코딩테스트 연습 - 해시 - 베스트앨범이라는 문제이다.

위 링크를 타고 문제를 읽어보면 생각보다 단순하지 않게 느껴질 것이다.

우선 아래는 직접 풀은 코드이다.

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) { //map에 있는 vector 정렬
    return a.second > b.second;
}

bool cmp2(pair<string,int> a, pair<string,int> b) { //vector정렬
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string,vector<pair<int,int>>> m;
    vector<pair<string,int>> v;
    for(int i = 0; i < genres.size(); i++) {
        if(m.find(genres[i]) == m.end()) { //처음 보는 장르인 경우
            vector<pair<int,int>> tmp; //벡터를 생성하여 번호와 재생 수를 저장
            tmp.push_back({i, plays[i]});
            m.insert({genres[i], tmp});
            v.push_back({genres[i], plays[i]}); //벡터에 추가
        }
        else { //이미 있는 장르인 경우
            m[genres[i]].push_back({i, plays[i]}); //map에 번호와 재생 수를 추가
            for(int j = 0; j < v.size(); j++) { //vector에서 같은 장르를 찾음
                if(genres[i] == v[j].first) {
                    v[j].second += plays[i]; //장르의 전체 재생 수 추가
                    break;
                }
            }
        }
    }
    sort(v.begin(), v.end(), cmp2); //장르별 전체 재생 수 정렬
    for(auto it = m.begin(); it != m.end(); it++) { //같은 장르의 각각 재생 수 정렬
        sort((*it).second.begin(),(*it).second.end(), cmp);
    }
    for(auto it = v.begin(); it != v.end(); it++) { //장르별 재생 수가 많은 순서대로 
        answer.push_back(m[(*it).first][0].first); //첫 번째 많은 재생 수 추가
        if(m[(*it).first].size() > 1) { //만약 재생 수가 2개 이상인 경우 추가
            answer.push_back(m[(*it).first][1].first);
        }
    }
    
    
    
    return answer;
}

이 문제는 map과 vector를 이용하여 풀었다.

우선 이 문제에서는 장르별 전체 곡 수를 저장할 vector와 각 장르에서의 곡 번호와 재생 수를 저장할 map을 선언하였다.

map에는 첫 번째 인자로 string을 주어 장르 이름을 통해 접근할 수 있게하고 두 번째 인자로 vector<pair<int,int>>를 주어 곡 번호와 재생 수를 저장할 수 있게한다.

주어진 입력을 모두 돌며 map과 vector에 저장한 다음 sort함수를 이용해 장르별 재생 수와 각 장르에서의 곡별 재생수를 내림차순으로 정렬한다.

그 다음 정렬된 vector를 처음부터 돌며 가장 많은 곡을 순서대로 answer에 넣는다. 이때 한 장르의 전체 곡 수가 1개일 수 있으므로 if문을 이용해 장르의 곡 수가 2개 이상인지 확인하고 추가한다.

이 문제를 풀며 코드도 깔끔하게 작성하지 못하였고 풀이 방식도 간결하지 못하다고 느꼈지만 효용성을 채점하는 부분이 없고 정확성 채점만 존재했기 때문에 vector, map을 모두 이용하여 푸는 방법 밖에 떠올리지 못했다.

이 문제에서 중요했던 스킬은 iterator를 사용하는 것과 vmap에서 type으로 또 다른 vector를 넣어 이를 이용하는 방식이 관건이었다. 직접 작성하면서도 헷갈리는 부분이 굉장히 많았고 풀이는 처음에 맞았지만 i와 j를 잘 못 쓰는 바람에 시간이 조금 더 걸렸었다. c++을 활용한 코딩테스트 문제를 풀 때 vector는 기본이고 set과 map을 활용해야하는 문제가 굉장히 많다고 느끼기 때문에 c++의 STL을 잘 활용할 수 있는 공부가 필요하다고 생각한다. 문제를 풀고 다른 사람들의 풀이를 보고 더 짧은 코드는 어떻게 돌아가는지 이해하는 것도 중요한 것 같다.

programmers.co.kr/learn/courses/30/lessons/64064#

처음 문제를 잘 이해하지 못하여 접근방법을 잘못 알았고 아래에 첨부한 풀이도 비효율적이지만 오랜 시간을 들여 풀었기 때문에 그대로 첨부하였다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int answer;
bool visit[9];
set<string> rst;
void dfs(int n, vector<string> &user_id, vector<string> &banned_id, string s) {
    if(n == banned_id.size()) {
        sort(s.begin(), s.end());
        rst.insert(s);
        return;
    }
    string now = banned_id[n];
    for(int i = 0; i < user_id.size(); i++) {
        if(visit[i] || now.size() != user_id[i].size()) continue;
        int chk = 0;
        for(int j = 0; j < now.size(); j++) {
            if(now[j] == '*') continue;
            if(user_id[i][j] != now[j]) {
                chk = 1;
                break;
            }
        }
        if(!chk) {
            visit[i] = 1;
            dfs(n+1, user_id, banned_id, s + to_string(i));
            visit[i] = 0;
        }
    }
    return;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    dfs(0, user_id, banned_id, "");
    answer = rst.size();
    return answer;
}

처음에는 그래프를 그려 2-sat으로 이분매칭을 이용하여 풀려고 했으나 뜻대로 되지 않아 백트래킹을 이용하여 풀었다. 

ban사용자를 하나씩 선택하여 방문하지 않은 user중 일치하는 것이 있는지 확인한 후 재귀적으로 반복한다. dfs함수의 맨 마지막 인자인 string은 지금까지 일치된 사용자의 인덱스 번호이다. 사용자를 모두 찾은 경우 string s를 정렬하여 set에 집어 넣는다. 이 과정은 중복이 일어나지 않게 하기 위해서이다. 모든 과정을 끝낸 후 set의 사이즈를 리턴하면 된다.

programmers.co.kr/learn/courses/30/lessons/64065

이 문제에서는 각 집합을 탐색하며 숫자인지를 판별하고 검색될 때마다 검색된 횟수를 1씩 올려주는 방식으로 풀이했다.

#include <string>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) { //sort 비교 함수
    return a.second > b.second; //검색횟수가 많은 순서대로 저장
}

vector<int> solution(string s) {
    vector<int> answer;
    char num[100001] = {0}; //숫자를 만들 배열
    vector<int> arr;
    vector<pair<int,int>> tmpans;
    bool visit[501]; //탐색한지 확인
    int cnt = 0;
    int idx = 0;
    for(int i = 0; i < s.length(); i++) {
            if(s[i] == '{') { //시작시 메모리 초기화
                idx = 0;
                memset(visit, 0, sizeof(visit));
                memset(num, 0, sizeof(num));
            }
            else if(s[i] == '}') {
                if(num[0] != 0) { //숫자생성
                    int n = atoi(num);
                    memset(num, 0, sizeof(num));
                    arr.push_back(n);
                    cnt++; //한 집합에서 숫자의 개수 추가
                }
                else {//입력의 마지막 '}'인 경우
                    continue;
                }
                if(arr.size() != 0) { //집합에 숫자가 있는 경우
                    if(cnt < tmpans.size()) { //만약 지금까지 탐색한 튜플의 원소가 더 많은 경우 검색횟수만 +1
                        for(int j = 0; j < tmpans.size(); j++) {
                            for(int k = 0; k < arr.size(); k++) {
                                if(tmpans[j].first == arr[k]) {
                                    tmpans[j].second++;
                                }
                            }
                        }
                    }
                    else { //새로운 튜플 원소가 나타난 경우
                        for(int j = 0; j < arr.size(); j++) {
                            int chk = 0;
                            int k;
                            for(k = 0; k < tmpans.size(); k++) {
                                if(visit[k]) { //탐색한 튜플 원소 건너뜀
                                    continue;
                                }
                                if(tmpans[k].first == arr[j]) { //이미 검색된 원소는 검색횟수 1추가
                                    tmpans[k].second++;
                                    visit[k] = 1;
                                    chk = 1;
                                    break;
                                }
                            }
                            if(!chk && (k == tmpans.size())) { //새로운 원소 추가하고 검색횟수 1로 설정
                                tmpans.push_back({arr[j], 1});
                            }
                        }
                    }
                    memset(visit, 0, sizeof(visit));
                }
                else continue;
                cnt = 0;
                arr.clear();
                idx = 0;
                memset(num, 0, sizeof(num));
            }
            else if(s[i] ==  ',') {
                if(num[0] != 0) { //집합을 구분 짓는 ','이 아닌 경우
                    int n = atoi(num);
                    arr.push_back(n);
                    memset(num, 0, sizeof(num));
                    cnt++;
                }
                memset(num, 0, sizeof(num));
                idx = 0;
                continue;
            }
            else { //10진수 숫자 생성
                num[idx++] = s[i];
            }
    }
    sort(tmpans.begin(), tmpans.end(), cmp); //검색 횟수 순으로 정렬
    for(int i = 0; i < tmpans.size(); i++) { //정답 옮겨 저장
        answer.push_back(tmpans[i].first); 
    }
    return answer;
}

임시 정답 vector를 선언하고 원소와 검색된 횟수를 저장한다. 모든 집합을 탐색하며 기존에 검색된 원소 수보다 많은 경우 모두 1씩 증가하고 없는 원소는 추가하여준다. 입력값을 모두 탐색한 후 가장 많은 빈도의 원소 순으로 정렬되므로 정답에는 원소만 옮겨 저장해준다. 

programmers.co.kr/learn/courses/30/lessons/64061

이 문제에서는 vector로 입력이 주어진다. 주의해야할 점은 주어진 NxN 행렬에서 탐색하려는 행만 접근하는 것이 아닌 0번 행부터 N-1번 행까지 0이 아닐 때 까지 열을 모두 탐색해야한다는 점이다. 즉 한 행은 뽑기 기계의 깊이를 나타낸다. 아래는 풀이한 코드이다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    vector<int> arr;
    int answer = 0;
    for(int i = 0; i < moves.size(); i++) { 
        int idx = moves[i]-1; //탐색하고자 하는 열
        int doll = 0;
        for(int j = 0; j < board.size(); j++) { //해당 각 행에서 인형이 있는지 확인
            if(board[j][idx] != 0) { //인형이 발견한 경우
                doll = board[j][idx];
                board[j][idx] = 0;
                break;
            }
        }
        if(doll == 0) continue; //인형을 발견하지 못한 경우
        if(arr.size() == 0) { //뽑은 인형을 담는 바구니가 비어있는 경우
            arr.push_back(doll);
            continue;
        }
        else if(arr.back() == doll) { //바구니 맨 위에있는 인형과 뽑은 인형이 같은 경우
            arr.pop_back();
            answer+=2; //이미 있는 인형과 발견한 인형 모두 사라지므로 +2
        }
        else arr.push_back(doll); //바구니 맨 위에있는 인형과 뽑은 인형이 다른 경우
        
    }
    return answer;
}

뽑으려고하는 열들은 move라는 vector로 주어진다. 뽑기를 진행하며 주어진 행렬 board의 해당 열에 인형이 있는지 확인한다. 인형이 있는 경우 바구니인 arr의 마지막 값과 비교한다. 만약 arr가 비어있는 경우 push_back을 하고 arr의 마지막 값이 인형과 같은 경우 두 인형 모두 터져서 사라지고 인형 2개가 사라지므로 answer를 2 올려준다. 마지마으로 인형이 다른 경우 마지막에 push_back해준다.

최단 경로를 탐색하는 알고리즘에서 한 정점에서 다른 모든 정점까지 탐색하는 알고리즘에는 대표적으로 두 가지가 있다. 하나는 다익스트라 알고리즘이고 다른 하나는 벨만-포드 알고리즘이다. 두 알고리즘의 차이점은 대부분 알다시피 간선의 가중치에 음수가 있느냐(벨만-포드) 없느냐(다익스트라)이다.

이 점은 누구나 알고 있지만 실제로 코드에서 어떠한 차이점이 있는 지는 설명만 보고 알기 어려워 비교를 해보려고 한다.

우선 대표적인 다익스트라 알고리즘 문제인 백준 1753번 문제를 푼 알고리즘이다.

www.acmicpc.net/problem/1753 

다익스트라 알고리즘

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int INF = 2123456789;

struct edge { //간선의 가중치와 목적지 구조체
	int w, v;
};

vector<edge> g[20001]; //그래프 간선 구조체
int dist[20001]; //시작점에서 모든 정점까지의 최단 경로를 저장할 dp배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
	int V, E, K; cin >> V >> E >> K;
	for(int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({w, v}); //그래프의 간선 정보 입력
	}

	fill(dist + 1, dist + 1 + V, INF); //시작점에서 모든 정점은 아직 방문하지 않았으므로 INF로 초기화

	using P = pair<int,int>; //pair 표현 간소화
	priority_queue<P, vector<P>, greater<P>> pq; //최소힙 구현
	pq.push({0, K}); //처음 시작점 push
	dist[K] = 0; //시작점은 최단 경로 0으로 초기화
	while(!pq.empty()) { //더 이상 갱신할 최단 경로가 없을 때까지
		P tmp = pq.top(); pq.pop(); //새로 뻗을 수 있는 간선 중에 가중치가 가장 작은 값
		int cur_w = tmp.first;
		int cur = tmp.second;

		if(dist[cur] < cur_w) continue; //최소값 아닐 경우 건너뛰기

		for(edge next : g[cur]) { //새로 뻗은 간선에서 뻗을 수 있는 모든 간선에 대하여
			if(dist[next.v] > dist[cur] + next.w) { //최소값을 갱신할 수 있으면 갱신하고 우선순위 큐에 push
				dist[next.v] = dist[cur] + next.w;
				pq.push({dist[next.v], next.v});
			}
		}
	}
	for(int i = 1; i <= V; i++) {
		if(dist[i] == INF) //최단 경로가 없으면 INF
			cout << "INF" << '\n';
		else
			cout << dist[i] << '\n'; //최단 경로가 있으면 최단 경로 출력
	}
	return 0;
}

www.acmicpc.net/problem/11657

벨만 포드 알고리즘

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

struct edge { //간선의 정보를 저장할 구조체
    long long w, v;
};

int INF = 987654321;
vector<edge> g[501]; //그래프 간선 표현 vector배열
long long dist[501]; //최소값을 저장할 dp배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        long long a, b, c; cin >> a >> b >> c;
        g[a].push_back({c, b}); //간선 정보 저장
    }
    fill(dist, dist+N+1, INF); //모든 정점까지 최단 경로 INF로 초기화
    dist[1] = 0; //시작점 최단 경로 0으로 초기화

    for(int i = 1; i <= N; i++) { //N번 반복
        for(int j = 1; j <= N; j++) { //j에서 다른 정점으로 뻗을 수 있는 간선의 정점 최솟값 갱신
            if(dist[j] == INF) continue; //최단 경로가 없는 경우 건너뛰기
            for(edge next : g[j]) { //j에서 뻗을 수 있는 간선에 대하여
                if(i < N) { //모든 정점 갱신할 수 있는 N-1번 반복까지는 최단 경로 갱신
                    if(dist[next.v] > dist[j] + next.w) { //최단 경로 갱신
                        dist[next.v] = dist[j] + next.w;
                    }
                }
                else { //만약 모든 최단 경로를 갱신한 다음 N번째에도 최솟값을 갱신하는 경우
                    if(dist[next.v] > dist[j] + next.w) { //무한히 최단 경로를 갱신하므로 -1출력하고 프로그램 종료
                        cout << -1 << '\n';
                        return 0;
                    }
                }
                
            }
        }
    }
    for(int i = 2; i <= N; i++) {
        if(dist[i] == INF) cout << -1 <<'\n'; //최단 경로가 없는 경우 -1 출력
        else cout << dist[i] <<'\n'; //최단 경로 출력
    }

}

위와 같이 두 가지 알고리즘을 작성해보았다.

간선에 음의 가중치가 없는 다익스트라의 경우 최솟값이 무한히 갱신되는 경우가 없기 때문에

우선순위 큐를 이용하여 갱신할 최단 경로가 존재하지 않을 때까지만 반복하면 된다.

하지만 음의 가중치가 있는 벨만 포드의 경우 다익스트라처럼 우선순위 큐를 사용할 경우

최단 경로를 갱신하는 경우 우선선위 큐에 push하고 큐가 모두 빌 때까지 반복하므로 아래 그림과 같이 1에서 4까지의 경로가 2-3-4를 순환하면서 최단경로가  -1씩 무한히 갱신될 수 있다.

따라서 정점의 수 N에 대하여 간선의 수는 최대 N(N-1)이므로 모든 정점에 대하여 N-1번 반복하면 모두 갱신할 수 있게 된다. 따라서 N번째 반복에서 최단 경로가 또 한 번 갱신된다면 이는 위의 그림처럼 무한히 갱신되는 경우가 된다.

이러한 이유가 벨만 포드에서 우선순위 큐가 빌 때까지가 반복문의 조건이 아닌 이유이다.