꼽행착오

주어진 문제는 위와 같다. 최대 100 개의 도시가 주어지고, 도시 간 이동이 가능한 버스 노선들이 주어졌을 때 모든 도시 간 이동 시의 최소 비용을 구하는 것이다. 최단 경로 탐색을 위한 알고리즘은 다익스트라, 벨만 포드, A* 탐색 등 여러 가지가 있지만 위와 같이 모든 노드 간 최단 경로를 구하기 위한 알고리즘으로 문제의 이름과 같은 플로이드 와샬 알고리즘이 있다.

플로이드 와샬 알고리즘에 대해 내가 기억하고 있는 것은, 노드 간 경로 가중치를 테이블에 저장하고 경로가 존재하지 않는 경우는 INF 값으로 저장한다. 그 뒤 스텝 별로 중간에 다른 노드를 경유하며 경로 가중치를 업데이트하는 방식으로 기억하고 있었다. 하지만 내가 기억하고 있는 알고리즘의 로직은 너무 모호해 문제 풀이에 적용할 수 없었고 따로 플로이드 와샬 알고리즘을 찾아본 뒤 문제를 해결했다.

플로이드 와샬 알고리즘

플로이드 와샬 알고리즘을 간단하게 설명하면, O(|V|^3) 의 시간 복잡도를 갖는 모든 쌍 최단 경로 탐색 알고리즘이다. 매 스텝 별로 X to Y (X, Y 는 노드) 경로의 가중치를 업데이트 해야 하므로 O(|V| ^ 2) 를 매 스텝 별로 실행하고, 각 스텝은 경유할 노드를 순차적으로 적용하므로 O(|V| ^ 2 * |V|) 의 시간 복잡도를 갖게 된다.

k = 0 일 때, 해당 테이블은 노드를 경유하지 않고 i - j 간 경로를 표현한 것이다.

k = 1 일 때, 변경된 table[2][3] 값은, 기존의 node(2) -> node(3) 의 경로 가중치는 3이고, 노드 1번을 경유한 node(2) -> node(1) -> node(3) 의 가중치 합이 4 + (-2) 이므로 새로운 값이 업데이트된 것을 볼 수 있다.

k = 2 일 때, node(4) -> node(1) 의 경로와 node(4) -> node(3) 의 경로가 2번 노드를 경유함으로 인해 가중치 값이 업데이트된 것을 확인할 수 있다.

이와 같이 경유할 노드를 변경해 가며 경로 가중치 값을 업데이트해 나가면 최종적으로 모든 노드 쌍 간의 최단 경로를 구할 수 있게 된다.

알고리즘을 적용한 코드는 3개의 for 문을 중첩함으로써 간단하게 구현이 가능하고, 이를 적용해 문제 해결에 사용한 코드는 다음과 같다.

#include <iostream>
using namespace std;

const int CITY = 100;
const int INF = 123456789;

int city, bus;
int dist[CITY + 1][CITY + 1];

void initialize() {
    for (int i = 1; i <= city; i++) {
        for (int j = 1; j <= city; j++) {
            dist[i][j] = INF;
        }
    }
}

void input() {
    cin >> city >> bus;
    initialize();

    for (int i = 0; i < bus; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = dist[a][b] < c ? dist[a][b] : c;
    }
}

void output() {
    for (int i = 1; i <= city; i++) {
        for (int j = 1; j <= city; j++) {
            if (dist[i][j] == INF) {
                cout << "0 ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << "\n";
    }
}

void solve() {
    for (int k = 1; k <= city; k++) {
        for (int i = 1; i <= city; i++) {
            for (int j = 1; j <= city; j++) {
                if (i == j)
                    continue;
                int k_dist = dist[i][k] + dist[k][j];
                dist[i][j] = dist[i][j] < k_dist ? dist[i][j] : k_dist;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();

    solve();

    output();
}

# Reference.

주어진 문제는 위와 같다. 수열의 크기 n 이 주어지고, 수열을 이루는 1 ~ n 까지 정수가 하나씩 순서대로 주어진다. 이 때, 스택을 가지고 주어진 수열을 만들기 위해 필요한 연산을 한 줄에 하나씩 출력한다.

스택은 LIFO 구조로, push / pop 연산을 통해 자료를 저장하고 뺄 수 있다. 스택으로 수열을 만들기 위해서 필요한 조건은, 주어진 정수가 항상 스택에 저장된 top 값보다 크거나 같아야 한다는 것이다. 만약 스택의 top 에 저장된 값보다 작은 정수가 주어졌을 때는 그 값을 찾기 위해 스택에서 여러 번 pop 을 해야 하므로, 이 문제에서 주어진 조건을 만족할 수 없다.

때문에 문제의 풀이 방식은 간단하다. 주어진 정수가 스택에 저장된 top 의 값보다 크다면 값들을 push 해 주어진 정수가 스택에 저장되도록 한다. 그 뒤 스택의 top 에 있는 값을 꺼내면 된다. 만약 주어진 정수가 스택에 저장된 top 값과 같다면 그 값을 pop 연산을 통해 바로 꺼낼 수 있다. 이 때 문제는, 이미 스택에 push 된 값이 다시 push 될 수 있다는 점이다.

예를 들어, [1, 2, 3, 4] 의 순서로 push 가 이뤄지고 [4, 3] 순서로 pop 이 되었을 때 스택의 top 에 저장된 값은 '2' 이다. 이 때 '6' 이라는 정수가 주어지면 스택의 top 보다 큰 '3' 부터 '6' 까지 [3, 4, 5, 6] 순서로 push 를 하게 된다. 하지만 이 경우에 이미 [3, 4] 라는 값들은 push / pop 이 된 값이므로 이를 다시 수행하지 않도록 따로 기록을 해야 한다.

그래서 이 문제에서 추가적으로 활용하는 변수로 스택에 마지막으로 push 된 값을 기록한다. 만약 위의 경우에 마지막으로 push 한 값이 '4' 임을 안다면 '6' 이 주어졌을 때, [5, 6] 만 push 를 하면 됨을 알 수 있다. 따라서 중복되는 push / pop 연산이 이루어지지 않는다.

이러한 풀이로 작성한 소스 코드는 다음과 같다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int N, num, cur;
stack<int> s;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string ans = "";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> num;

        if (cur < num) {
            for (int k = cur + 1; k <= num; k++) {
                s.push(k);
                ans += "+\n";
            }
            cur = num;
        }
        else if (s.top() != num) {
            ans = "NO\n";
            break;
        }

        s.pop();
        ans += "-\n";
    }

    cout << ans;
}

문제 풀이 중간에 불가능한 값이 입력될 경우 ans 라는 문자열을 "NO" 로 바꾸고 반복을 종료한다. 그렇지 않을 경우 정상적으로 연산의 순서가 ans 에 저장될 것이다. 이를 콘솔에 출력함으로써 주어진 문제에 대한 답을 얻을 수 있다.

주어진 문제는 위와 같다. 2차원 행렬에서 (0, 0) -> (M - 1, N - 1) 까지의 최단 거리를 구하는 문제에 특별한 이동 방식이 추가된 형태이다. 특별한 이동 방식은 체스에서 나이트가 움직이는 방식과 같고 문제에서 정의한 K 만큼 이러한 방식으로 이동할 수 있다.

일반적인 BFS 문제는 큐를 사용해 각각의 이동으로 인한 현재 위치를 저장하고 그 위치가 목적지에 도달하면 종료하게 된다. 이 때, 동일한 위치에 대해서 재방문을 할 필요가 없기 때문에 각 위치 (x, y) 의 방문 여부를 저장한다. 이 문제는 이에 더해 그 위치까지 몇 번의 이동 능력을 사용했는 지가 중요하기 때문에 (x, y) 위치 + 이동 능력 사용 횟수 를 기준으로 방문 여부를 체크하면 해결할 수 있다.

이러한 풀이로 작성한 소스 코드는 다음과 같다.

#include <iostream>
#include <queue>

using namespace std;

const int MAX_SIZE = 200;

struct POINT {
    int r, c;
    int horse, cnt;

    POINT(int r, int c, int horse, int cnt) : r(r), c(c), horse(horse), cnt(cnt) {}
};

int dr[4] = {1, 0, -1, 0}, dc[4] = {0, 1, 0, -1};
int hr[8] = {-1, -2, -2, -1, 1, 2, 2, 1}, hc[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

int N, M, K;
int map[MAX_SIZE][MAX_SIZE];
bool vis[MAX_SIZE][MAX_SIZE][31];

void input() {
    cin >> K;
    cin >> M >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
}

int solve() {
    queue<POINT> que;

    que.push(POINT(0, 0, 0, 0));
    while (que.size()) {
        POINT top = que.front();
        que.pop();

        if (top.r == N - 1 && top.c == M - 1) {
            return top.cnt;
        }

        if (vis[top.r][top.c][top.horse])
            continue;
        vis[top.r][top.c][top.horse] = true;

        if (top.horse < K) {
            for (int k = 0; k < 8; k++) {
                int nr = top.r + hr[k], nc = top.c + hc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M)
                    continue;
                if (map[nr][nc] || vis[nr][nc][top.horse + 1])
                    continue;
                que.push(POINT(nr, nc, top.horse + 1, top.cnt + 1));
            }
        }
        for (int k = 0; k < 4; k++) {
            int nr = top.r + dr[k], nc = top.c + dc[k];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M)
                continue;
            if (map[nr][nc] || vis[nr][nc][top.horse])
                continue;
            que.push(POINT(nr, nc, top.horse, top.cnt + 1));
        }
    }

    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    cout << solve();

    return 0;
}

solve() 함수에서 기존 BFS 소스 코드와 차이점이 있다면, if (top.horse < K) 로 시작되는 분기문이다. POINT 구조체의 horse 는 현재까지 이동 능력의 사용 횟수이며 이 횟수가 K 보다 작다면 특별한 이동 방식으로 이동할 수 있도록 한다. 또한, bool 타입 3차원 행렬 vis 에서 마지막 인덱스로 horse 값을 사용해 해당 위치까지 가는 동안 사용한 이동 능력의 횟수를 확인해 재방문을 막는다.