240521: 클래스 4 은장 달성 🥈

2024-05-21

클래스 4 은장 달성

오늘은 Solved.ac 클래스 4의 은장을 달성했다.
금장까지는 18문제 남았다. 이제 슬슬 생각을 꽤 오래 해야하는 문제가 출제된다.
골드 하위 ~ 상위 구간의 문제다.

---

모각코를 운영하게 되었다.

목표를 설정하고 Top-down 방식으로 위의 목표를 이루기 위해 해야할 일을 정리해봤다.
이렇게 하면 10단계에는 정말 사소한 일이 된다고 한다. 나도 심심해서 해봤는데 정말 뜬금없는게 나왔다.
바로 '스터디 그룹 만들기' 그리고 그 바로 밑 단계가 '그냥 내가 직접 만들기' 가 되었다. 그렇게 갑작스럽게 '모각코'를 구하게 되었고. 생각보다 훨씬 많이 사람들이 신청을 해줘서 얼떨결에 운영하게 되었다. 그래도 한번 운영해보는거 잘하자! 라는 생각에 나름의 규칙도 만들고 열정있게 리드했다.

이번주 목요일에 약 6명이서 첫 모임을 가질 예정이다. 느슨한 유대감을 가지는 건 좋은 것 같다.

---

최근 풀었던 문제 정리

실버 상위:

• N과 M (5) (15654)
• 트리의 부모 찾기 (11725)
• N과 M (9) (15663)
• 트리 순회 (1991)
• 스티커 (9465)
  골드:
• 트리의 지름 (1967)
• 파티 (1238)
• 웜홀 (1865)
• 트리의 지름(심화) (1167)
• 후위 표기식 (1918)

N과 M (5) - 백트래킹

N과 M 시리즈 문제는 여기서 한번만 다루도록 하겠다. N과 M 시리즈는 전형적인 백트래킹 문제다.
조건을 만족하는 모든 수열을 구하는 문제인데, "N개의 자연수 중에서 M개를 고른 수열" 이런 식이다.

문제는 이런 조건을 for문으로 처리할 수 없다. 왜냐하면 M에 따라서 for문이 2중이 되거나 3중이 되어야 하는데 이건 불가능하기 때문이다. 따라서 재귀 DFS, 백트래킹을 사용한다.

기초적인 문제다. 조건에 맞는 모든 수열을 고르고 백트래킹하고 재귀로 반복한다...
문제에서 수열을 사전 순으로 증가하는 순서로 출력하라고 해서, 주어지는 입력을 오름차순 정렬하고 재귀를 돌렸다.

// 백준: N과 M (5)
// https://www.acmicpc.net/problem/15654
// 2024-05-16

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

int N, M;

void dfs(vector<int> &path, vector<int> &arr, vector<bool> &visited) {
    if (path.size() == M) {
        for (const int &num : path) {
            cout << num << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            path.push_back(arr[i]);
            visited[i] = true;
            dfs(path, arr, visited);
            path.pop_back(); // 백트래킹
            visited[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M; // N개의 수에서 M개를 고른 수열
    vector<int> arr(N);
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    vector<int> path;
    vector<bool> visited(N, false);
    dfs(path, arr, visited);
    return 0;
}

// 백준: N과 M (9)
// https://www.acmicpc.net/problem/15663
// 2024-05-16

/*
주의: std::unique는 **연속된 중복 요소**를 제거함
*/

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> saved_path;

void dfs(vector<int> &path, vector<int> &arr, vector<bool> &visited) {
    if (path.size() == M) {
        saved_path.push_back(path);
        return;
    }

    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            path.push_back(arr[i]);
            visited[i] = true;
            dfs(path, arr, visited);
            path.pop_back(); // 백트래킹
            visited[i] = false;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    // sort(arr.begin(), arr.end());
    vector<bool> visited(N, false);
    vector<int> path;
    dfs(path, arr, visited);
    sort(saved_path.begin(), saved_path.end());                                       // std::unique는 연속된 중복 요소를 제거함.
    saved_path.erase(unique(saved_path.begin(), saved_path.end()), saved_path.end()); // 중복 제거
    for (const auto &path : saved_path) {
        for (const auto &next : path) {
            cout << next << " ";
        }
        cout << "\n";
    }
    return 0;
}

주의해야 할 점: std::unique는 연속된 중복 요소를 제거하기 때문에. 목적에 따라 사용하기 전에 대상 배열을 sort해야 한다.

---

트리의 부모 찾기 (그래프 이론, 트리)

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하는 문제다.

처음엔 문제를 보고 약간 당황했다. 트리라고 함은 루트에서부터 뻗어 나가는 사이클이 없는 연결 그래프인데, 어떤 트리가 주어지든 그냥 자기 위쪽에 있는 부모를 구하는 건 너무 쉬운 일 아닌가?

근데 이건 내 착각이었다.
문제에서는 입력 데이터로 노드간의 간선 정보를 줬을 뿐이지. 어떠한 연결 관계 데이터도 준 적 없다. 그저 입력된 순으로 노드가 뻗어 있을거라는 건 문제를 읽은 나의 착각이었다.

문제에서 입력으로 주어진 데이터는 간선 정보일 뿐이다. 어느 방향인지는 주어진 적이 없다.

따라서, 1번 노드에서부터 그래프 탐색을 하면서 부모를 찾아 나가는 간단한 로직으로 풀 수 있었다.

// 백준: 트리의 부모 찾기
// https://www.acmicpc.net/problem/11725
// 2024-05-16

/*
입력으로 주어진 데이터는 간선 정보일 뿐이다.
어느 방향인지는 주어진적이 없다. 그저 문제를 읽은 나의 착각일 뿐..
*/

#include <iostream>
#include <vector>
using namespace std;

void dfs(int start, vector<int> &parents, vector<vector<int>> &adj) {
    for (const auto &next : adj[start]) {
        if (parents[next] == -1) { // 아직 탐색되지 않았으면
            parents[next] = start; // 부모 삽입
            dfs(next, parents, adj);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> adj(N + 1, vector<int>());
    vector<int> parents(N + 1, -1);
    for (int i = 0; i < N - 1; ++i) {
        int from, to;
        cin >> from >> to;
        adj[from].push_back(to);
        adj[to].push_back(from);
    }

    dfs(1, parents, adj);
    for (int i = 2; i < parents.size(); ++i) {
        cout << parents[i] << "\n";
    }

    return 0;
}

---

트리 순회 (트리, 재귀)

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

전위 순회란: 루트 -> 왼쪽 자식 -> 오른쪽 자식 순서.
중위 순회란: 왼쪽 -> 루트 -> 오른쪽
후위 순회란: 왼쪽 -> 오른쪽 -> 루트 순서로 순회함을 뜻한다.

트리에 대한 기본적인 구현과 재귀 순회 방식을 배울 수 있는 문제였다.
트리 구조체에 값 정보, 그리고 왼쪽 자식 노드의 포인터 정보, 오른쪽 자식 노드의 포인터 정보를 담아서 저장했다.

또, 동적 선언과 정적 선언에 대한 이해도 명확히 했다. 처음엔 입력한 노드 정보를 저장하는 map을 선언하고 트리의 노드 정보를 new 키워드로 선언하면서 그 포인터 값을 map에 넣었다.

그니까, 트리 노드 정보를 힙에 생성하고 그 주소만 map에 저장했다.
이후 레퍼런스를 찾아보니까 동적 선언보다 정적 선언이 더 빠르다고 해서 new 키워드를 없애고, map에 저장하는 노드 값을 포인터가 아니라 Node 구조체 그 자체로 받도록 했다.

그리고 구조체의 멤버 변수에 접근할 때, 포인터로 접근하면 -> Arrow operator 멤버 접근 연산자를 사용했는데. 포인터가 가리키는 객체의 멤버 변수에 접근할때는 ->를 쓰고, 객체의 멤버에 접근할 때는 dot operator '.' 을 사용하는 점에 유의하여 수정했다.

// 백준: 트리 순회
// https://www.acmicpc.net/problem/1991
// 2024-05-16

/*
트리 구현을 배울 수 있는 교육적인 문제.
*/

#include <iostream>
#include <unordered_map>
using namespace std;

struct TreeNode {
    char val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode()
        : val(0), left(nullptr), right(nullptr) {} // unordered_map에서 새로운 키를 생성할 때, 먼저 기본 생성자로 TreeNode를 생성하고 거기에 값을 대입하기 때문에. 기본 생성자 자체를 누락시키면
                                                   // tuple:1811:7: error: no matching constructor for initialization of 'TreeNode' 에러가 남.
};

void preOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    cout << root->val;
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    inOrder(root->left);
    cout << root->val;
    inOrder(root->right);
}

void postOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    unordered_map<char, TreeNode> nodes;
    for (int i = 0; i < N; ++i) {
        char node, left, right;
        cin >> node >> left >> right;
        if (nodes.find(node) == nodes.end()) { // 새로운 노드
            nodes[node] = TreeNode(node);
        }
        if (left != '.' && nodes.find(left) == nodes.end()) {
            nodes[left] = TreeNode(left);
        }
        if (right != '.' && nodes.find(right) == nodes.end()) {
            nodes[right] = TreeNode(right);
        }

        nodes[node].left = (left == '.') ? nullptr : &nodes[left];
        nodes[node].right = (right == '.') ? nullptr : &nodes[right];
    }

    TreeNode *root = &nodes['A'];
    // 순회
    preOrder(root);
    cout << "\n";
    inOrder(root);
    cout << "\n";
    postOrder(root);
    cout << "\n";

    // for (auto &node : nodes) {
    //     delete node.second;
    // }

    return 0;
}

---

스티커 (DP)

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

처음에는 그리디거나 완전탐색 문제인 줄 알았으나, 의외로 다이나믹 프로그래밍 문제였다. 행의 개수가 2로 고정되어 있다는 점에서 DP임을 바로 알았어야 했다.

이 문제가 DP인 이유는 다음과 같다:
매 분기점마다 두가지의 선택을 할 수 있고. 각 선택은 다음 해에 영향을 준다.
2차원 dp 배열을 memoization으로 선언하고 dp[r][c] r이 0일때와 1일때로 나눠서 (위쪽 스티커를 떼기로 선택했을 때, 혹은 아래쪽 스티커를 떼기로 선택했을 때의 값을 저장하고)

c가 0일때부터 시작해서 열의 개수까지 돌리면서 최적의 선택을 저장해나가면 되는 문제다.

따라서 이제 점화식만 도출해내면 되는데. 현재의 선택이 미래에 어떤 영향을 미치는 지 생각해야 한다.
매 분기점마다 두가지의 선택을 할 수 있다: 현재 열 c의 위쪽 스티커를 떼거나, 아래쪽 스티커를 떼거나
현재 열의 위쪽 스티커를 뗀다면, 다음 열에서는 위쪽 스티커를 뗄 수 없다. 따라서 현재 열에서 위쪽 스티커를 뗀다면, 이전 열의 위쪽 스티커를 뗀 최댓값을 사용하면 안된다.

그렇다고 이전 열의 아래쪽 스티커를 뗀 최댓값을 무조건 사용해도 안된다. 왜냐하면, 현재 열의 위쪽 스티커를 떼면 이전 열은 아래 스티커를 떼는 게 확정이라고 착각하기 쉽지만,
현재 열의 위쪽 스티커를 뗀 것으로 인해 이전 열의 아래 스티커를 떼면, 결국엔 전-전-열의 아래 스티커를 뗄 수 없기 때문에, 전-전-열의 아래 스티커가 높은 점수를 가진 경우
중간 열의 스티커 위쪽, 아래쪽을 모두 떼지 않는 방법이 유효할 수 있기 때문이다.

즉.

1. 현재 행의 위쪽 스티커를 떼고, 다음 행의 아래쪽 스티커를 떼거나
2. 현재 행의 아래쪽 스티커를 떼고, 다음 행의 위쪽 스티커를 떼거나
3. 현재 행의 위쪽 스티커를 떼고, 다음 행을 뜯지 않고, 다다음 행의 아래쪽 스티커를 떼거나 (만약 중간 행의 스티커를 뜯는다면 무조건 아래쪽이었을 거고, 그러면 끝 행의 아래쪽 스티커를 뗄 수없다)
4. 현재 행의 아래쪽 스티커를 떼고, 다음 행을 뜯지 않고, 다다음 행의 위쪽 스티커를 떼거나.

총 4개의 방법이 있다.

따라서
dp[0][c] = 마지막으로 위쪽 스티커를 뗐을 때의 최댓값.
dp[1][c] = 마지막으로 아래쪽 스티커를 뗐을 때의 최솟값.

dp[0][c] = max(dp[1][c-1], dp[1][c-2]) + 현재 스티커 점수
dp[1][c] = max(dp[0][c-1], dp[0][c-2]) + 현재 스티커 점수

// 백준: 스티커
// https://www.acmicpc.net/problem/9465
// 2024-05-16

/*
풀기전에 데이터의 크기를 봤어야 했다. 완전 탐색으로는 풀 수 없다.
DP로 풀어야 한다.

현재의 선택이 미래에 어떤 영향을 미치는 지 생각해야 한다.
매 분기점마다 두가지의 선택을 할 수 있다: 현재 열 c의 위쪽 스티커를 떼거나, 아래쪽 스티커를 떼거나
현재 열의 위쪽 스티커를 뗀다면, 다음 열에서는 위쪽 스티커를 뗄 수 없다. 따라서 현재 열에서 위쪽 스티커를 뗀다면, 이전 열의 위쪽 스티커를 뗀 최댓값을 사용하면 안된다.
그렇다고 이전 열의 아래쪽 스티커를 뗀 최댓값을 무조건 사용해도 안된다. 왜냐하면, 현재 열의 위쪽 스티커를 떼면 이전 열은 아래 스티커를 떼는 게 확정이라고 착각하기 쉽지만,
현재 열의 위쪽 스티커를 뗀 것으로 인해 이전 열의 아래 스티커를 떼면, 결국엔 전-전-열의 아래 스티커를 뗄 수 없기 때문에, 전-전-열의 아래 스티커가 높은 점수를 가진 경우
중간 열의 스티커 위쪽, 아래쪽을 모두 떼지 않는 방법이 유효할 수 있기 때문이다.

즉.
1. 현재 행의 위쪽 스티커를 떼고, 다음 행의 아래쪽 스티커를 떼거나
2. 현재 행의 아래쪽 스티커를 떼고, 다음 행의 위쪽 스티커를 떼거나
3. 현재 행의 위쪽 스티커를 떼고, 다음 행을 뜯지 않고, 다다음 행의 아래쪽 스티커를 떼거나 (만약 중간 행의 스티커를 뜯는다면 무조건 아래쪽이었을 거고, 그러면 끝 행의 아래쪽 스티커를 뗄 수없다)
4. 현재 행의 아래쪽 스티커를 떼고, 다음 행을 뜯지 않고, 다다음 행의 위쪽 스티커를 떼거나.

총 4개의 방법이 있다.

따라서
dp[0][c] = 마지막으로 위쪽 스티커를 뗐을 때의 최댓값.
dp[1][c] = 마지막으로 아래쪽 스티커를 뗐을 때의 최솟값.

dp[0][c] = max(dp[1][c-1], dp[1][c-2]) + 현재 스티커 점수
dp[1][c] = max(dp[0][c-1], dp[0][c-2]) + 현재 스티커 점수
*/

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC;
    cin >> TC;
    while (TC--) {
        int n;
        cin >> n;
        vector<vector<int>> sticker(2, vector<int>(n));
        vector<vector<int>> dp(2, vector<int>(n));
        for (int r = 0; r < 2; ++r) { // 스티커는 2*n 사이즈
            for (int c = 0; c < n; ++c) {
                cin >> sticker[r][c];
            }
        }

        // BASE CASE
        dp[0][0] = sticker[0][0]; // 위 스티커를 뗀 값
        dp[1][0] = sticker[1][0]; // 아래 스티커를 뗀 값

        if (n > 1) {
            dp[0][1] = sticker[1][0] + sticker[0][1];
            dp[1][1] = sticker[0][0] + sticker[1][1];
        }

        for (int c = 2; c < n; ++c) {
            dp[0][c] = sticker[0][c] + max(dp[1][c - 1], dp[1][c - 2]);
            dp[1][c] = sticker[1][c] + max(dp[0][c - 1], dp[0][c - 2]);
        }

        cout << max(dp[0][n - 1], dp[1][n - 1]) << "\n";
    }
    return 0;
}

---

트리의 지름 (트리, 그래프 탐색)

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이 문제는 DFS든 BFS든 풀 수 있을 것 같은데 왜 태그에 DFS만 있는 지 모르겠다.
나는 BFS와 DFS를 둘 다 써봤다. (문제가 총 두 문제다)

첫 문제는 조금 TLE가 널널한 문제고, 심화 문제는 TLE가 빡빡한 문제다 (노드 수가 더 많다)

처음 문제는 백트래킹 + DFS로 가능한 최대 길이를 업데이트 하면서 풀었다.

문제의 데이터를 좀 보다보니까, 하나의 규칙을 발견했다. (사실 당연한건데)
무조건 트리의 지름을 구성하는 끝과 끝 노드는 잎새 노드일수밖에 없다. 왜냐면 특정 간선이 음수 가중치를 가지지 않는 이상 한 단계라도 더 뒤로 빠지는 게 길다는 건 직관적으로 알 수 있다.

따라서, 나는 완전 탐색보다는 조금이라도 최적화 하고 싶어서 주어지는 입력 데이터에서 잎새 노드만을 특정하고. 모든 leaf node들에 대해서 DFS 탐색했다.

// 백준: 트리의 지름
// https://www.acmicpc.net/problem/1967
// 2024-05-17

/*
무조건 잎새 노드 <-> 잎새 노드(자식이 없는 노드) 만 최댓값이 될 수 있다.
각 잎새 노드에서부터 가능한 끝 지점까지 DFS 탐색하고, 백트래킹으로 모든 경우의 수에 대해 max_score을 업데이트 한다.

PS. 트리는 사이클이 없는 연결 그래프이므로, 두 노드 사이의 경로는 유일하다.
따라서, 임의의 노드에서 가장 먼 노드를 찾으면, 이 노드는 지름을 구성하는 끝 점중 하나가 된다.
즉, 임의의 노드에서 가장 먼 노드를 찾고. 그 노드에서 가장 먼 노드까지의 거리가 지름의 길이가 된다.
*/

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
vector<vector<pair<int, int>>> adj;
int max_score = 0;

void dfs(int current_node, int length, vector<bool> &visited) {
    // current_node가 잎새 노드인지 확인하거나..

    for (const auto &next : adj[current_node]) {
        if (!visited[next.first]) { // 아직 방문하지 않았다면
            visited[next.first] = true;
            dfs(next.first, length + next.second, visited);
            visited[next.first] = false; // 백트래킹
        }
    }

    // 끝에서 업데이트 (여기에 도달하는 경우는 마지막 노드밖에 없다)
    max_score = max(max_score, length);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<bool> check_leaf_nodes(n + 1, true);
    adj.assign(n + 1, vector<pair<int, int>>()); // 인접 노드, 가중치
    for (int i = 1; i < n; ++i) {
        int parent_node, children_node, v;
        cin >> parent_node >> children_node >> v;
        adj[parent_node].push_back({children_node, v});
        adj[children_node].push_back({parent_node, v});
        check_leaf_nodes[parent_node] = false; // 잎새 노드가 아니라고 체크
    }

    vector<int> leaf_nodes;
    for (int i = 1; i < n + 1; ++i) {
        if (check_leaf_nodes[i])
            leaf_nodes.push_back(i);
    }
    int SIZE = leaf_nodes.size();
    for (int i = 0; i < SIZE; ++i) {
        // 모든 잎새 노드에서부터 시작해서. 끝에 도달할 때 현재까지의 점수를 기록하고 백트래킹
        vector<bool> visited(n + 1, false);
        visited[leaf_nodes[i]] = true; // 시작 지점 방문 체크
        dfs(leaf_nodes[i], 0, visited);
    }

    cout << max_score;

    return 0;
};

트리의 지름 심화

트리의 지름 심화 문제는 시도는 안해봤지만 위와 같은 로직으로 구현 했을경우 TLE가 났을 것이다.
트리는 사이클이 없는. 즉, 두 노드간의 경로가 유일한 연결 그래프이므로 임의의 점 A를 고르고 A에서 제일 먼 노드 B를 찾으면 노드 B는 지름을 구성하는 끝 노드 중 하나임을 알 수 있다.

하나의 지름 노드를 찾으면 다음은 쉽다. 지름을 구성하는 끝 노드 B에서 제일 먼 노드 C를 찾는 것이다. 그러면 노드 B <-> 노드 C의 거리는 트리의 지름이 된다.

이 간단한 방법으로 두번의 그래프 탐색을 통해 문제를 해결할 수 있다.
또 DP 쓰는 방법이 있다고 하던데 ... 이건 일단 스킵

// 백준: 트리의 지름
// https://www.acmicpc.net/problem/1167
// 2024-05-19

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
vector<vector<pair<int, int>>> adj;
int V;

pair<int, int> bfs(int start) {
    pair<int, int> farthest_node = {0, 0};
    queue<pair<int, int>> q;
    vector<bool> visited(V + 1, false);
    q.push({0, start}); // 가중치, 노드
    visited[start] = true;

    while (!q.empty()) {
        int cur_node = q.front().second;
        int cur_weight = q.front().first;
        q.pop();

        if (farthest_node.first < cur_weight)
            farthest_node = {cur_weight, cur_node};

        for (const auto &next : adj[cur_node]) {
            int next_node = next.second;
            int weight = next.first;
            if (!visited[next_node]) {
                q.push({cur_weight + weight, next_node});
                visited[next_node] = true;
            }
        }
    }

    return farthest_node;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> V;
    adj.assign(V + 1, vector<pair<int, int>>()); // 거리, 정점
    for (int i = 0; i < V; ++i) {
        int cur_node;
        cin >> cur_node;
        while (true) {
            int dest_node, value;
            cin >> dest_node;
            if (dest_node == -1)
                break;
            cin >> value;
            adj[cur_node].push_back({value, dest_node});
            adj[dest_node].push_back({value, cur_node}); // 양방향으로 추가
        }
    }

    // 임의의 점에서 가장 먼 노드 A를 구한다.
    // 노드 A에서 가장 먼 노드 B를 구한다.
    // A -> B가 트리의 지름
    pair<int, int> farthest_node = bfs(1);
    cout << bfs(farthest_node.second).first;
    return 0;
}

---

파티 (데이크스트라, 최단 경로)

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

단방향 도로로 연결되어 있는 마을 사이에서 파티가 열리는 마을 X까지 왕복하는데 제일 오래 걸리는 학생을 구하는 문제이다.

다익스트라 알고리즘은 특정 노드에 대해 다른 모든 노드까지의 최단 경로를 구하는 문제이기 때문에. 가장 naive하게 각 노드에 대해서 다익스트라 알고리즘을 돌리면 문제를 풀 수 있었다.

근데, 여기서 더 참신한 방법이 있었다.
나는 비록 이 방법으로 풀진 않았지만. 간선을 모두 역방향으로 입력받고 파티 마을에서 다익스트라를 사용하면 사실상 모든 정점에서 파티 마을까지 가는 최단비용을 다익스트라 n번으로 구한 효과와 같다. 엄청 참신한 해결법.

single-source shortest path"와 "single-destination shortest path" 의 상관관계를 잘 안다면 쉽게 풀 수 있는 문제라고 한다.

single-source shortest path = 단일 출발점 최단 경로 (즉, 특정 노드에 대해 모든 노드까지의 거리)
single-destination shortest path = 단일 도착점 최단 경로 (즉, 모든 노드에 대해 도착점까지의 거리)

그리고 여기서 말하는 상관관계란.. 단일 출발점 최단 경로의 간선 정보를 역방향으로 입력 받으면 사실상 single-destination shortest path와 같다는 것.

이것은 single-source shortest path의 간선 정보가 양방향이어도 적용된다.
교육적인 문제.

// 백준: 파티
// https://www.acmicpc.net/problem/1238
// 2024-05-19

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define INF (~0U >> 2)
using namespace std;

int N, M, X; // 마을(학생) 수 N, 단방향 도로 M, 파티 마을 X

vector<int> dijkstra(int start_node, vector<vector<pair<int, int>>> &adj) { // 다익스트라 알고리즘으로 최단 거리를 탐색한다. 가중치가 동일하지 않으므로 BFS를 사용할 수 없다.
    vector<int> dist(N + 1, INF);
    dist[start_node] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 거리, 정점
    pq.push({0, start_node});

    while (!pq.empty()) {
        int cur_node = pq.top().second;
        int cur_dist = pq.top().first;
        pq.pop();

        if (cur_dist > dist[cur_node])
            continue; // 이미 처리된 노드 무시

        for (const auto &next : adj[cur_node]) {
            int next_node = next.first;
            int next_dist = cur_dist + next.second;
            if (dist[next_node] > next_dist) {
                dist[next_node] = next_dist;
                pq.push({next_dist, next_node});
            }
        }
    }

    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M >> X;
    vector<vector<pair<int, int>>> adj(N + 1, vector<pair<int, int>>());
    for (int i = 0; i < M; ++i) {
        int start_node, end_node, v;
        cin >> start_node >> end_node >> v;
        adj[start_node].push_back({end_node, v});
    }

    // 먼저 파티 마을에서 각 노드까지 얼마나 걸리는 지 저장
    vector<int> dist_sum = dijkstra(X, adj);

    // 그런 다음, 각 노드에서 파티 마을까지의 최소 거리를 합산
    for (int i = 1; i <= N; ++i) {
        if (i == X)
            continue; // 파티 마을 무시
        dist_sum[i] += dijkstra(i, adj)[X];
    }

    cout << *max_element(dist_sum.begin() + 1, dist_sum.end());
    return 0;
}

---

웜홀 (벨만-포드, 최단경로)

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

매우 교육적인 문제.

이 문제는 전형적인 벨만-포드 알고리즘을 사용해서 음수 가중치가 있는 그래프에서의 최단 경로를 알아내는 문제라고 생각하기 쉽지만 사실 중요한 부분이 다르다.

답을 도출할 필요가 없다. 그저 음의 사이클이 존재하는 지, 존재하지 않는 지만 판독하면 된다. 음의 사이클이 존재하지 않을때의 최단 거리를 도출할 필요가 없다. 따라서 일반적인 벨만-포드 알고리즘을 변형해서 쉽게 풀 수 있다.

물론 변형하지 않아도 풀 수 있지만 .. 변형해야 더 쉽게 풀 수 있다.

벨만 포드 알고리즘은 다익스트라 알고리즘과는 다르다. 다익스트라 알고리즘은 현재 노드에 대해서 가장 가까운 노드를 현재 알려진 값과 비교해 업데이트 하면서 나아가지만, 벨만 포드 알고리즘은 모든 노드에 대해서 인접한 노드를 현재 알려진 값과 비교해 업데이트 한다.

다익스트라 알고리즘은 인접한 노드를 priority_queue에 넣고 가장 비용이 적은 것부터 비교하면서 탐색하고.
벨만-포드는 정점 -1의 수만큼 인접한 노드를 탐색해 비교하고. 완화(relaxation) 과정을 모두 거치고 한번의 탐색을 더 해서, 알려진 값이 업데이트가 되면 음의 사이클이 존재한다고 판단한다.

여기서 중요한 점은 dist 배열의 INF와 관련해서이다.. 원래의 벨만-포드 알고리즘 구현은 dist 배열을 모두 INF로 초기화하고. 벨만-포드는 single-source shortest path 알고리즘이기 때문에 시작 노드의 거리 배열만 0으로 초기화하고 시작한다.

그리고 각 비교 과정에서 현재의 비교 대상의 dist가 INF가 아님을 확인함으로써 시작 지점에서부터 도달한 노드임을 확인할 수 있다. 만약 현재의 비교 대상의 dist가 INF가 아님을 확인하지 않으면 음의 가중치가 있을 때 INF - weight이 되면서 값이 업데이트 될 수 있다.

그니까 원래의 벨만-포드 구현해서는 dist 배열을 마치 방문 배열처럼도 사용하고 있기 때문에. 시작 지점에 대해서 정확하게 최단 거리를 구할 수 있다.

그리고 이게 문제가 된다. 이 문제에서 주어지는 그래프는 모든 지점이 연결 되어있다는 보장이 없다!
특정 간선이 존재하지 않아서 노드 1에서 시작했을 때도 노드 10에 도달할 수 있다는 보장을 할 수 없다. 이건 문제를 풀 때 흔하게 할 수 있는 오해였다. 근데 만약에 노드 10과 연결되어있는 다른 노드들 사이에서 음의 사이클이 존재한다면. 단순히 1번 노드로 벨만-포드 알고리즘을 돌리는 것으론 모든 음의 사이클 가능성에 대해 탐색할 수 없다.

따라서, 방문 배열을 없애야 한다 if문에서 거리 배열이 INF일때는 업데이트를 하지 않는 부분을 없애야 한다. INF에 값이 + 됐을 때 오버플로우가 나지 않도록 적당한 값으로 INF를 타협하고. 배열이 INF인 상태에서도 값이 업데이트 될 수 있도록 한다. 이러면 최단 거리는 구하지 못할 수도 있지만 음의 사이클이 존재하는 부분이 있는지는 정확하게 탐색할 수 있다.

매우 교육적인 문제였다.

// 백준: 웜홀
// https://www.acmicpc.net/problem/1865
// 2024-05-19

/* 벨만-포드 알고리즘 기초 문제
다익스트라와 유사하지만, 인접한 정점부터 탐색하는 게 아니라 그냥 싸그리 탐색 해도 됨.
주의: 모든 지점이 연결 되어있다는 보장이 없다. 연결 그래프라면 아무 곳이나 탐색해도 음의 순환이 발견되겠지만. 그게 아니다.
만약 dist[i] = INF 일때의 갱신을 허용하지 않는다면. 시작 노드와 연결이 끊겨 있는 그래프가 갱신되지 않아서 음의 사이클을 발견 못 할수도 있다.
따라서, INF의 값이 오버플로우가 나지 않게 타협하고, INF 일때도 음수 가중치를 만나면 갱신이 될 수 있도록 한다. 이렇게 해야 임의의 노드에서 1번 탐색해도 음의 사이클을 탐지할 수 있다.
*/

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
#define INF (~0U >> 2)
using namespace std;

vector<int> dist;

bool bellmanFord(int start, int V, vector<tuple<int, int, int>> &edges) {
    dist.assign(V + 1, INF);
    dist[start] = 0; // 시작 지점 (이건 이제 아무 의미가 없다)

    for (int i = 0; i < V - 1; ++i) { // V - 1번 완화(Relaxation)
        for (const auto &edge : edges) {
            int s, e, t;
            tie(s, e, t) = edge;

            if (dist[s] + t < dist[e]) {
                dist[e] = dist[s] + t;
            }
        }
    }

    // 음의 사이클 확인
    for (const auto &edge : edges) {
        int s, e, t;
        tie(s, e, t) = edge;

        if (dist[s] != INF && dist[s] + t < dist[e])
            return true; // 음의 사이클 있음
    }

    return false; // 음의 사이클 없음
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC;
    cin >> TC;
    while (TC--) {
        int N; // 지점의 수
        int M; // 도로 개수
        int W; // 웜홀 개수 (음수 가중치)
        cin >> N >> M >> W;
        vector<tuple<int, int, int>> edges;

        // 주의: (본문) 도로는 방향이 없으며, 웜홀은 방향이 있다.
        for (int i = 0; i < M; ++i) {
            int S, E, T; // 시작 지점, 도착 지점, 가중치
            cin >> S >> E >> T;
            edges.push_back(make_tuple(S, E, T));
            edges.push_back(make_tuple(E, S, T));
        }
        for (int i = 0; i < W; ++i) {
            int S, E, T; // 가중치 *-1 유의
            cin >> S >> E >> T;
            edges.push_back(make_tuple(S, E, T * -1));
        }

        if (bellmanFord(1, N, edges))
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

---

후위 표기식 (스택, 자료구조)

중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하는 유명한 문제.
후위 표기식에 대해서 제대로 알게 된것도 이 문제 덕분이다.

스택을 이용해서 이 과정을 처리할 수 있는데 한국어로 "차량기지 알고리즘" 이라고 한다.
output string과 연산자를 임시 저장할 스택을 만들고 다음의 규칙에 따라 로직을 작성하면 된다

1. 숫자, 변수 등은 바로 출력
2. 연산자는 스택의 .top() 연산자의 우선순위보다 클동안 .push() 이외는 .pop()

스포를 당하고 풀어서 그런지 골드 2 치곤 쉬웠다. 근데 후위 표기식이 뭔지도 모르고, 스택을 사용해야 한다는 것도 몰랐다면 꽤 어려웠을 것 같다.. 특히 괄호 처리가 ..

어려운 문제.

// 백준: 후위 표기식
// https://www.acmicpc.net/problem/1918
// 2024-05-21

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

int precedence(char op) {
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    if (op == '(' || op == ')')
        return 3;
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string infix;
    cin >> infix;
    int SIZE = infix.length();
    string output;
    stack<char> operatorStack;
    for (int i = 0; i < SIZE; ++i) {
        char cur = infix[i];
        int priority = precedence(cur);
        /*
        출력 stack과 연산자 stack 사용
        1. 숫자, 변수 등은 출력 stack으로 바로 이동
        2. 연산자는 연산자 스택의 .top() 보다 우선순위가 클동안 .push. 이외 .top() 반복
        */
        if (priority == 0) { // 연산자 아님
            output.push_back(cur);
        } else {                                  // 연산자
            if (priority == 1 || priority == 2) { // + - * /
                if (operatorStack.empty())
                    operatorStack.push(cur);
                else {
                    while (!operatorStack.empty()) {
                        if (operatorStack.top() == '(')
                            break;
                        if (precedence(operatorStack.top()) < priority)
                            break;
                        output.push_back(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                }
            } else if (priority == 3) { // 괄호
                if (cur == '(')
                    operatorStack.push(cur);
                else {
                    while (!operatorStack.empty()) {
                        if (operatorStack.top() == '(') {
                            operatorStack.pop();
                            break;
                        }
                        output.push_back(operatorStack.top());
                        operatorStack.pop();
                    }
                }
            }
        }
    }

    // 스택 정리
    while (!operatorStack.empty()) {
        output.push_back(operatorStack.top());
        operatorStack.pop();
    }
    cout << output;
    return 0;
}

---

끝.