C++로 두 개의 문자 스택을 모두 비울 수 있는지 확인하는 방법

문제 개요

총 2n개의 문자가 있고, 각 문자에는 1부터 n 사이의 정수가 하나씩 적혀 있습니다. 같은 숫자는 정확히 두 개의 문자에만 등장합니다. 이 문자들은 m개의 스택에 나누어 쌓여 있으며, i번째 스택에는 stacks[i]에 해당하는 문자들이 들어 있습니다.

목표는 다음 규칙에 따라 모든 스택을 비우는 것입니다.

임의의 두 스택을 선택하고, 두 스택에서 각각 맨 위의 문자를 제거합니다.
이때 제거한 두 문자에는 반드시 동일한 숫자가 적혀 있어야 합니다.

이러한 방식으로 m개의 스택을 모두 비울 수 있다면 true를 출력하고, 그렇지 않다면 false를 반환하면 됩니다.

예시

예를 들어 n = 3, m = 2, stacks = {{2, 1, 3}, {2, 1, 3}}이 입력으로 주어졌다고 가정해 봅시다. 이 경우 결과는 true입니다.

두 개의 스택이 존재하고, 각 스택에는 숫자 2, 1, 3이 순서대로 적힌 문자가 쌓여 있습니다. 두 스택에서 같은 숫자가 적힌 문자끼리 짝을 지어 제거하면 모든 스택을 깨끗하게 비울 수 있습니다.

해결 접근 방법

이 문제는 그래프의 의존 관계를 활용한 위상 정렬(topological sort) 방식으로 해결할 수 있습니다. 스택 안에서 어떤 문자가 제거되려면 그 위에 놓인 문자들이 먼저 처리되어야 한다는 점에 착안합니다. 구체적인 단계는 다음과 같습니다.

2차원 배열 dp와 배열 tvec을 선언합니다.
모든 스택을 순회하면서, 스택 내에서 인접한 두 문자 사이의 선행 관계를 dp에 기록하고, tvec에는 각 문자가 기다려야 하는 횟수를 누적합니다.
1부터 n까지의 각 숫자를 시작점으로 삼아 큐를 이용한 탐색을 진행합니다. 아직 방문하지 않았고 대기 중인 의존 관계(tvec 값)가 0인 노드를 발견하면, 해당 노드가 가리키는 다음 노드들의 tvec 값을 1씩 줄이고 큐에 추가합니다.
탐색이 끝난 후 모든 tvec 값이 0인지 검사합니다. 0이 아닌 값이 하나라도 남아 있다면 스택을 전부 비우는 것이 불가능하므로 false를, 그렇지 않으면 true를 반환합니다.

2D 배열 dp 선언
배열 tvec 선언
i := 0으로 초기화하고, i < m인 동안 i를 1씩 증가시키며 반복:
    k := stacks[i]의 크기
    j := 0으로 초기화하고, j < k인 동안 j를 1씩 증가시키며 반복:
        j > 0이면:
            dp[stacks[i, j]] 끝에 p 삽입
            tvec[p]를 1 증가
        p := stacks[i, j]
배열 tp 선언
i := 1로 초기화하고, i <= n인 동안 i를 1씩 증가시키며 반복:
    큐 q 선언
    q에 i 삽입
    q가 비어 있지 않은 동안 반복:
        tp[q의 첫 번째 원소]가 false이고 tvec[q의 첫 번째 원소]가 0이면:
            dp[q의 첫 번째 원소]의 각 원소 next에 대해:
                tvec[next]를 1 감소
                next를 q에 삽입
            tp[q의 첫 번째 원소] := true
        q에서 첫 번째 원소 삭제
i := 1로 초기화하고, i <= n인 동안 i를 1씩 증가시키며 반복:
    tvec[i]가 0이 아니면:
        false 반환
true 반환

예제 코드

아래 구현을 통해 더 자세히 이해해 봅시다.

#include <bits/stdc++.h>
using namespace std;

bool solve(int n, int m, vector<vector<int>> stacks){
    vector<vector<int>> dp(n + 1);
    vector<int> tvec(n + 1);
    for(int i = 0; i < m; i++){
        int k = stacks[i].size();
        int p;
        for(int j = 0; j < k; j++){
            if(j > 0){
                dp[stacks[i][j]].push_back(p);
                tvec[p]++;
            }
            p = stacks[i][j];
        }
    }
    vector<bool> tp(n + 1);
    for(int i = 1; i <= n; i++){
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            if(!tp[q.front()] && tvec[q.front()] == 0){
                for(auto next: dp[q.front()]){
                    tvec[next]--;
                    q.push(next);
                }
                tp[q.front()] = true;
            }
            q.pop();
        }
    }
    for(int i = 1; i <= n; i++){
        if(tvec[i] != 0){
            return false;
        }
    }
    return true;
}
int main() {
    int n = 3, m = 2;
    vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}};
    cout << solve(n, m, stacks);
    return 0;
}

입력

3, 2, {{2, 1, 3}, {2, 1, 3}}