99클럽 코테스터디 36일차 TIL BOJ- 도미노

도미노

BOJ Gold V BruteForce
문제 링크

문제 설명

세준이가 가지고 있는 도미노는 약간 다르다. 세준이는 도미노를 N2개 가지고 있다. 따라서 N=2라면, 세준이는 (1,1), (1,2), (2,1), (2,2) 이렇게 총 N2개를 가지고 있는 것이다.

세준이는 이 도미노를 가지고 도미노미도마도라는 게임을 하려고 한다. 이 게임은 김민오가 만들었다.

이 게임에서 도미노는 N*N크기의 보드에 놓여져 있다. i번째 행, j번째 열에는 (i,j)라고 쓰여 있는 도미노가 놓여져 있다. 플레이어는 도미노를 정확하게 N개를 골라야 하는데, 선택한 도미노를 두 개가 같은 행에서 고르고, 선택한 도미노를 같은 열에서 고르면 안 된다는 조건이 있다. 또, 고른 도미노를 가지고 사이클을 만들 수 있다. 사이클을 만드는 방법은, 도미노 A와 B가 있을 때, A의 두 번째 숫자와 B의 첫 번째 수가 같으면 된다. 그리고 사이클을 이루는 첫 번째 도미노의 처음 숫자와 마지막 도미노의 둘째 숫자가 같으면 된다.

예를 들어, (1,3), (3,2), (2,4), (4,1)을 골라서 사이클을 만들 수 있다.

N개의 도미노를 고르면 이러한 사이클이 한 개 또는 그 이상의 그룹이 나온다. (1,1)와 같은 도미노는 자기 자신으로 사이클을 이루므로 하나의 그룹이다.

게임의 조건 중에 각 행과 열에서 중복되면 안되는 조건이 있기 때문에, 항상 사이클을 이룰 수 있다.

모든 도미노는 그 뒷면에 숫자가 쓰여 있다. 이 게임에서 점수를 계산할 때는 자기가 고른 도미노의 뒷면에 쓰여 있는 수를 모두 곱한다. 그 다음에 만약 사이클 그룹의 개수가 짝수가 되면 그 수에 -1을 곱한다.

세준이는 자기가 이 게임에서 얻을 수 있는 최대 점수와 최소 점수가 궁금해 졌다.

도미노의 개수와 도미노 뒷면에 쓰여 있는 수가 주어질 때, 세준이가 얻을 수 있는 최대 점수와 최소 점수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. N은 6보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 도미노에 쓰여 있는 수가 주어진다. i행 j열에 쓰여 있는 수는 도미노 (i,j)의 뒷 면에 쓰여 있는 수이다. 도미노의 뒷면에는 0부터 9까지의 수와 A부터 I까지 알파벳 대문자가 쓰여 있고, A부터 I까지 문자가 의미하는 것은 -1부터 -9까지이다.

출력
첫째 줄에 세준이가 얻을 수 있는 최소 점수, 둘째 줄에 세준이가 얻을 수 있는 최대 점수를 출력한다.

행과 열이 겹치지 않도록 숫자를 고르면서 최대 최소 값을 고르는 문제
사이클이란 하나의 숫자의 열 인덱스와 다른 하나의 숫자의 행의 인덱스가 같고 첫번째 숫자의 행 인덱스와 마지막 숫자의 열 인덱스가 같으면 된다.
(1, 3), (2, 2), (3, 1) 일 경우 사이클이 두개 발생한다고 생각하면 된다.

문제 풀이

문제를 이해하는 것이 가장 어려웠어서 문제를 이해하면 다음은 비교적 쉬웠다.
숫자의 범위 자체가 그리 크지않고, 주어지는 크기도 6^2 라서 완전탐색을 하면 되는 문제였다.

코드

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

using namespace std;

int dominoes[7][7], N, resMax=-1e9, resMin=1e9;
bool visited[7] = {false, };

void ckAll(int curRow, int value, vector<pair<int, int>>& par) {
    if (curRow == N) {
        int cycleCnt = 0;
        vector<bool> nodeVisited(N, false);

        for (int i = 0; i < N; i++) {
            if (!nodeVisited[i]) {
                int current = i;
                while (!nodeVisited[current]) {
                    nodeVisited[current] = true;
                    int next = par[current].second - 1;
                    if (next == current) break;
                    current = next;
                }
                cycleCnt++;
            }
        }

        if (cycleCnt % 2 == 0 && cycleCnt > 0) {
            value *= -1;
        }

        resMax = max(value, resMax);
        resMin = min(value, resMin);
        return;
    }

    for (int i=0; i<N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            par.push_back(make_pair(curRow+1, i+1));
            ckAll(curRow+1, value*dominoes[curRow][i], par);
            visited[i] = false;
            par.pop_back();
        }
    }
}

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

    cin >> N;
    string inputText;
    if (N == 1) {
        cin >> inputText;
        if ('A' <= inputText[0] && inputText[0] <= 'I') {
            cout << -1 * (inputText[0] - 'A' + 1) << "\n";
            cout << -1 * (inputText[0] - 'A' + 1) << "\n";
        } else {
            cout << -1 * (inputText[0] - '0') << "\n";
            cout << -1 * (inputText[0] - '0') << "\n";
        }
        return 0;
    }

    for (int i=0; i<N; i++) {
        cin >> inputText;
        int cnt=0;
        for (char c: inputText) {
            if (0 > c - 'A') {
                dominoes[i][cnt] = c - '0';
            } else {
                dominoes[i][cnt] = -(c-'A'+1);
            }
            cnt++;
        }
    }

    pair<int, int> tmp;
    vector<pair<int, int>> tmpV;
    // tmpV.push_back(tmp);
    ckAll(0, 1, tmpV);

    cout << resMin << "\n";
    cout << resMax << "\n";

    return 0;
}

회고

문제를 이해하면 이 문제에 대해서는 반은 해결한거나 다름 없었다 생각한다.
나는 문제가 잘 이해되지 않아 gpt 한테 예제를 보여줘 가며 설명해달라고 했고, 한시간에 걸쳐서 이해했다.
사이클의 대한 조건을 따지는 것이 조금 어려운 문제였다.