[SW Expert Academy] 1260. 화학물질 2

Posted on April 05, 2021

문제 :

유엔 화학 무기 조사단이 대량 살상 화학 무기를 만들기 위해 화학 물질들이 저장된 창고를 조사하게 되었다.창고에는 화학 물질 용기 n2개가 n x n으로 배열되어 있었다.유엔 조사단은 각 용기를 조사하여 2차원 배열에 그 정보를 저장하였다.빈 용기에 해당하는 원소는 ‘0’으로 저장하고, 화학 물질이 들어 있는 용기에 해당하는 용기는 화학 물질의 종류에 따라 ‘1’에서 ‘9’사이의 정수를 저장하였다.다음 그림은 창고의 화학 물질 현황을 9x9 배열에 저장한 예를 보여준다.

유엔 조사단은 화학 물질이 담긴 용기들로부터 2가지 사항을 발견하였다.

화학 물질이 담긴 용기들이 사각형을 이루고 있다. 또한, 사각형 내부에는 빈 용기가 없다.

예를 들어, 위의 그림에는 3개의 화학 물질이 담긴 용기들로 이루어진 사각형 A, B, C가 있다.

2개의 화학 물질이 담긴 용기들로 이루어진 사각형들 사이에는 빈 용기들이 있다.

예를 들어, 위의 그림에서 A와 B사이와 B와 C사이를 보면, 빈 용기를 나타내는 ‘0’ 원소들이 2개의 사각형 사이에 있는 것을 알 수 있다.

단, A와 C의 경우와 같이 대각선 상으로는 빈 용기가 없을 수도 있다.

또한 유엔 조사단은 화학 물질이 담긴 용기들로 이루어진 사각형들 사이에 특정한 관계가 있는 것을 추후 조사를 통해서 알아내었다.

그 관계는 바로 화학 물질이 든 용기들로 이루어진 각 사각형을 행렬이라고 여겨, 행렬 간의 곱셈을 수행하는 방식으로 화학 물질을 섞는 것이다.

즉, 2개의 행렬 원소 간 곱셈은 2개의 행렬 원소에 대응되는 화학 물질을 섞는 것이다.

단, 섞은 물질들을 합치는 데는 시간이 걸리지 않는다고 가정한다.

예를 들어, 그림에서 3개의 행렬 A, B, C의 차원이 각각 3x4, 2x3, 4x5이므로, 행렬간 곱셈을 수행하기 위해 반드시 BxAxC로 곱셈이 수행되어야 한다.

그러나 어떤 행렬들을 먼저 곱하는 것에 따라 행렬 원소간의 곱셈 수가 달라질 수 있다.

예를 들어, 위 그림에서 3개의 행렬 (A(3x4), B(2x3), C(4x5))의 곱셈을 살펴보면, (BA)C, 즉, B*A를 먼저 수행하고 그 결과 행렬을 C 와 곱하면, 64번의 원소간 곱셈이 수행된다.

그러나 B(AC)의 경우는 90번의 곱셈이 필요하다.

유엔 조사단의 시간을 절약하기 위해, 창고의 용기들에 대한 2차원 배열에서 행렬(화학 물질이 든 용기들로 이루어진 사각형)들을 찾아내고,

찾아낸 행렬들 간의 곱셈에 필요한 최소 원소간의 곱셈 수 (2개의 화학 물질이 든 용기를 섞는 작업의 수)를 찾는 프로그램을 작성하시오.

입력 :

맨 첫 줄에는 테스트 케이스의 개수가 주어진다.

그리고 테스트 케이스가 각 라인에 주어진다.

각 테스트 케이스는 (n+1) 줄로 구성되며, 첫 줄에는 양의 정수인 n이 주어지고, 다음 n줄에는 n x n 행렬이 (각 행이 한 줄에) 주어진다.

출력 :

각 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 행렬에서 추출된 부분 행렬들을 곱하는데 필요한 최소의 원소 간의 곱셈 수를 출력한다.

풀이 :

행렬의 최소 곱셈 DP 문제의 경우 알고리즘 수업시간에 다룬 적 있으나 역시,,, 시간이 흘러서 기억이 전혀 나지 않았고..ㅎㅎ 다시 공부하는 차원에 문제를 풀어보았다.

본 문제는 앞에서 말한 것 처럼 행렬의 최소 곱셈을 memorization을 활용하여 접근하면 쉽게 풀릴줄 알았으나,, 우선 배열을 탐색해서 찾은 행렬들을 곱셈이 가능하게 정렬하는 것 까지도 꽤나 귀찮은 과정이었다.

우선 내 코드의 경우 n*n 배열에서 0이 아닌 위치를 찾고 한 번도 탐색하지 않은 좌표인 경우(visit 배열이 false인 경우) 그 점을 기준으로 →, ↓ 방향으로 최대 길이를 찾은 후 최대 길이까지의 사각형 좌표들을 모두 visit 배열 true 변환 과정을 거쳐주었다. 이럴 경우 하나의 행렬의 행과 열의 길이를 구할 수 있다.
이후 행렬의 행, 열 길이를 담고 있는 벡터를 훑으면서 행렬들의 행과 열들의 길이를 인덱스로 가지는 배열 colused, rowused에 해당 인덱스의 길이를 가지는 행렬의 벡터 인덱스를 저장하는 방식으로 정리를 한 번 더 진행했다. → 이럴 경우 colused, rowused를 참조할 경우 자연스레 벡터들을 체인처럼 곱셈 순서를 찾아나갈 수 있다.
이렇게 행렬의 순서를 모두 찾아 벡터에 정렬했을 경우부터는 DP 과정이 시작된다.
점화식 ⇒ dp[i][j] = min(dp[i][k] + dp[k+1][j] + (행렬 i 행의 길이) * (행렬 k 열의 길이) * (행렬 j 열의 길이), dp[i][j]) (i≤k≤j)
점화식의 의미는 행렬 i에서 행렬 j까지의 최소 곱셈 횟수는 행렬 i에서 행렬 k까지의 최소 곱셈 횟수 더하기 행렬 k+1에서 행렬 j까지의 최소 곰셈 횟수에다가 두 분할 그룹의 곱셈 횟수를 더한 총 횟수들 중 가장 적은 값이라는 의미이다.
점화식 자체를 세우기가 매우 어렵다… dp는 정말 많이 풀어봐야 하는 것도 맞고 유사 형식의 점화식들을 익혀두면 빠르게 접근이 가능할 듯 하다.

코드 :

코드 보기/접기

#include<iostream>
#include<cstring>
#include<vector>
#include<utility>
#include<algorithm>

#define pii pair<int, int>

using namespace std;
bool visit[100][100];
int map[100][100], colused[100], rowused[100], dp[100][100], n;

pii bfs(int x, int y) {
    int cmpx = x + 1, cmpy = y + 1, distx = 1, disty = 1;

    while(1) {
        if(cmpx >= n) break;
        if(!map[cmpx][y]) break;
        distx++;
        cmpx++;
    }
    while(1) {
        if(cmpy >= n) break;
        if(!map[x][cmpy]) break;
        disty++;
        cmpy++;
    }
    
    for(int i=0; i<distx; i++)
        for(int j=0; j<disty; j++)
            visit[x + i][y + j] = true;
    
    return pii(distx, disty);
}

int testCase() {
    int input, idx;
    vector<pii> matvec, sortvec;
    cin >> n;
    memset(colused, -1, sizeof(colused));
    memset(visit, false, sizeof(visit));
    memset(dp, -1, sizeof(dp));
    
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(map[i][j] && !visit[i][j])
                matvec.push_back(bfs(i, j));
    
    int size = matvec.size();
    for(int i=0; i<size; i++){
        dp[i][i] = 0;
        colused[matvec[i].second] = i;
    }
    for(int i=0; i<size; i++){
        if(colused[matvec[i].first] == -1) idx = i;
        rowused[matvec[i].first] = i;
    }
    
    for(int i=0; i<size; i++) {
        sortvec.emplace_back(matvec[idx].first, matvec[idx].second);
        idx = rowused[matvec[idx].second];
    }
    
    for(int k=2; k<=size; k++)
        for(int i=0; i<=size-k; i++){
            int j = i + k - 1;
            for(int t=i; t<=j; t++){
                if(dp[i][j] == -1) dp[i][j] = dp[i][t] + dp[t+1][j] + sortvec[i].first * sortvec[t].second * sortvec[j].second;
                else dp[i][j] = min(dp[i][t] + dp[t +1][j] + sortvec[i].first * sortvec[t].second * sortvec[j].second, dp[i][j]);
            }
        }
    
    return dp[0][size -1];
}

int main(int argc, char** argv)
{
    int test_case, T;
    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        cout << '#' << test_case << ' ' << testCase() << '\n';
    }
    return 0;
}

Algorithm

algorithm SW Expert C++