【백준】- 14263. 카드 놓기

문제

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

14263번: 카드 놓기

풀이

카드가 쌓여 있는 관계를 잘 나타낸다면 방향성을 가지고 있는 그래프로 나타낼 수 있고, 위상 정렬로 풀 수 있게 됩니다. 아래와 같이 카드가 놓여 있다고 해 볼게요.

카드 $A$ 와 $D$ 는 처음부터 놓을 수 있습니다.

카드 $B$ 는 카드 $A$ 와 $D$ 가 놓여야 놓을 수 있습니다.

카드 $C$ 는 카드 $A$ 가 놓여야 놓을 수 있습니다.

카드 $E$ 는 카드 $B$ 가 놓여야 놓을 수 있습니다.

 

카드들의 관계가 단방향 관계임을 이용하여 위상 정렬로 풀어 봅시다. 이 때 진입 차수는 해당 카드를 놓기 위해 먼저 놓아야 하는 카드의 개수가 되겠죠!

카드의 영역

카드의 영역을 알면, 카드들의 관계를 알아낼 수 있습니다.

1. 카드의 영역은 카드가 채워진 모든 칸을 감쌀 수 있는 가장 작은 직사각형이 됩니다.
2. 카드 $A$ 의 영역 안에 카드 $B$ 를 이루는 칸이 있다면, 카드 $B$ 는 반드시 카드 $A$ 가 놓인 후에 놓일 수 있습니다.

예를 들어, 아래의 그림에서 카드 $A$ 의 영역은 빨간 선을 그은 부분이 됩니다.

카드의 영역을 조건을 만족하는 선에서 가장 작은 직사각형으로 하는 것은, 문제에서 요구한 사전순으로 앞서는 순서를 얻기 유리하게 하기 위함입니다. 이것도 예를 들어 보겠습니다.

위의 예시에서는 카드 $C$ 의 영역은 겉으로 보이는 두 칸이 전부일 수도 있고, 카드 $B$ 밑에 놓여 있다고 생각하면 여섯 칸일 수도 있습니다. 여기서 후자의 경우 카드 $B$ 와 $C$ 간에 의존성이 생깁니다. 카드 $B$ 를 놓으려면 반드시 카드 $C$ 를 먼저 놓아야 하는 제약이 더 생기는 것이죠. 실제로는 카드를 $A$ → $B$ → $C$ 의 순서로 놓을 수 있음에도 제약으로 인해 $A$ → $C$ → $B$ 로 놓을 수 밖에 없게 됩니다. 이렇듯 카드의 영역을 크게 잡을수록 의존하게 되는 관계가 많아져 최적의 답을 내기에 불리해지는 상황이 됩니다.

그래서 가능한 한 작은 영역을 잡아두고 문제를 푸는 것입니다.

 

카드들의 관계들을 알아내기 위해서 모든 카드들의 영역을 먼저 구한 후, 각 카드의 영역을 모두 돌아보면서 다른 종류의 카드가 있다면 그 카드의 진입 차수를 증가시켜 줍시다.

불가능한 경우

위상 정렬을 진행하기에 앞서 불가능한 경우가 있는데, 이 경우를 먼저 설명해 보겠습니다.

1. 카드들의 관계가 단방향 관계가 아니라, 서로 의존하는 사이클 관계가 있는 경우 불가능합니다. 사이클 관계를 가지는 카드에 해당하는 노드들은 진입 차수가 $0$ 이 되지 않아 방문하게 되지 않으니, 방문한 카드의 개수와 전체 카드의 개수와 비교하는 방법으로 이를 판별할 수 있습니다.
2. 카드의 영역 내에 빈 공간이 하나라도 있는 경우 불가능합니다. 카드가 직사각형 모양이 아니거나, 카드가 여러 개의 조각으로 나뉘어 있다는 뜻이 되는데, 두 카드가 같은 색을 가지는 경우는 없으므로 이런 경우가 생길 수가 없습니다.

위상 정렬은 그리디하게

불가능한 경우도 모두 알아냈으니 이제 위상 정렬을 해 봅시다. 위상 정렬은 여러분이 알고 있는 방식을 사용하시면 됩니다. 진입 차수가 $0$ 인 카드들을 올리고, 올린 카드와 연결되어 있는 카드들의 진입 차수를 $1$ 씩 감소시키면 됩니다. 여기까지는 평범하지만, 카드를 쌓는 순서는 사전순으로 가장 앞서야 함에 주의해야 합니다.

 

여기서 그리디한 접근 방법을 사용할 수 있는데, 쌓을 카드를 결정할 때마다 쌓을 수 있는 카드들 중 당장 사전순으로 가장 앞서는 카드를 선택해서 쌓는 것입니다.

이 방법은 항상 가장 합리적입니다. 왜냐하면, 사전순이라는 것은 아무리 뒤에 오는 문자들이 사전순으로 더 앞설지라도 앞에 오는 문자 하나가 사전순으로 뒤라면 그 단어는 무조건 사전순으로 더 뒤에 오는 것이 되기 때문입니다. 당장 사전순으로 뒤인 문자를 선택하면, 이후에 아무리 사전순으로 앞서는 문자들을 선택할 수 있더라도 항상 합리적이지 못한 경우가 됩니다.

 

같은 문자가 여러 개 있는 경우라면, 그 문자를 선택한 후 다음 단계에서 선택할 수 있는 문자가 어떤지에 대해서도 고려해 줘야 되지만, 문제 조건에 의하면 모든 카드의 색은 다르다는 것이 보장되므로 이 경우는 고려해 줄 필요가 없습니다. 따라서 위의 그리디한 전략은 항상 성립합니다.

 

사용할 수 있는 카드들 중 가장 사전순으로 앞선 카드를 찾아내기 위해서는, 기존의 큐를 사용하는 방식 대신 우선순위 큐를 사용하여 구현하는 것으로 문제를 해결할 수 있습니다.

코드

• C++17

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#define INF 100000
using namespace std;

struct Range {
    int sr, sc, er, ec;
};

char board[51][51];
int indegree[62];
Range range[62];
bool is_exist[62];
bool is_connected[62][62];
bool visited[62];
string answer;
bool success = true;
int element_count = 0;

int R, C;

int convert_char_to_int(char ch) {
    if (ch >= 'A' && ch <= 'Z') {
        return ch - 'A' + 10;
    }

    if (ch >= 'a' && ch <= 'z') {
        return ch - 'a' + 36;
    }

    return ch - '0';
}

char convert_int_to_char(int num) {
    if (num >= 10 && num <= 35) {
        return 'A' + num - 10;
    }

    if (num >= 36 && num <= 61) {
        return 'a' + num - 36;
    }

    return '0' + num;
}

void set_block_ranges() {
    for (int i = 0; i < 62; i++) {
        range[i] = {INF, INF, 0, 0};
    }

    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (board[r][c] == '.') continue;

            int i = convert_char_to_int(board[r][c]);
            is_exist[i] = true;

            range[i].sr = min(range[i].sr, r);
            range[i].sc = min(range[i].sc, c);
            range[i].er = max(range[i].er, r);
            range[i].ec = max(range[i].ec, c);
        }
    }
}

void count_elements() {
    for (int i = 0; i < 62; i++) {
        if (is_exist[i]) {
            element_count += 1;
        }
    }
}

void set_indegrees() {
    for (int i = 0; i < 62; i++) {
        if (!is_exist[i]) continue;

        for (int r = range[i].sr; r <= range[i].er; r++) {
            for (int c = range[i].sc; c <= range[i].ec; c++) {
                int cur = board[r][c];

                if (cur != convert_int_to_char(i)) {
                    if (cur == '.') {
                        success = false;
                        return;
                    }

                    int converted = convert_char_to_int(cur);

                    if (!is_connected[i][converted]) {
                        indegree[converted] += 1;
                        is_connected[i][converted] = true;
                    }
                }
            }
        }
    }
}

void traverse_and_print_result() {
    if (!success) return;

    priority_queue<int, vector<int>, greater<int>> pq;
    int visited_count = 0;

    for (int i = 0; i < 62; i++) {
        if (is_exist[i] && indegree[i] == 0) {
            pq.push(i);
        }
    }

    while (!pq.empty()) {
        int cur = pq.top();
        pq.pop();

        visited_count += 1;
        answer += convert_int_to_char(cur);

        for (int i = 0; i < 62; i++) {
            if (!is_connected[cur][i]) continue;

            is_connected[cur][i] = false;
            indegree[i] -= 1;

            if (indegree[i] == 0) {
                pq.push(i);
            }
        }
    }

    if (visited_count != element_count) {
        success = false;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> R >> C;

    for (int r = 0; r < R; r++) {
        cin >> board[r];
    }

    set_block_ranges();
    count_elements();
    set_indegrees();
    traverse_and_print_result();

    if (success) {
        cout << answer;
    } else {
        cout << -1;
    }
}