[ SWEA 1260 ] 화학물질2 (C++)

SWExpertAcademy의 화학물질2 (1260 / D6 ) 문제이다.

[ 문제풀이 ]

1) 1258번 문제였던 행렬찾기에서 한 단계 더 나아간 문제이다.

   기존에 행렬의 행의 길이, 열의 길이를 찾는 과정까지는 1258번 풀이와 동일하니 1258번 풀이로 행렬을 찾는 것 까지으

   설명은 대체하겠다.

   [ SWEA 1258 행렬찾기 풀이 ]

   1258번 문제에서는 행렬을 찾고 그 행렬의 행과 열, 그리고 넓이까지는 vector에 넣어서 저장해 주었는데

   이 문제를 풀 때에는 vector가 아닌 pair<int, int> 형 자료형을 만들어서 행과 열만 저장해 주었다.

   이 후, 구현 순서는 크게 2단계로 나눌 수 있다.

   1. 행렬의 순서 찾기

   2. 행렬의 곱 중, 최소 계산 횟수 찾기

   먼저 문제에서 행렬들의 곱셈에는 반드시 1개의 수행 가능한 행렬 곱셈 순서만 존재한다고 하였다.

   즉, 우리는 이 1개의 순서를 찾고자 하는 것이다.

   예를 들어서 행렬이 { 3 x 4 , 2 x 3 , 4 x 5 } 짜리 행렬이 있다고 생각해보자.

   행렬의 곱셈의 순서는 어떻게 될까 ???

   바로 (2x3) * (3x4) * (4x5) 이런 순서로 될 것이다. 왜냐하면 행렬에서 곱셈이 성립하기 위해서는

   앞에 행렬의 열과 뒤에 행렬의 행이 같아야 한다.

   즉, (2x3) * (3x4) 에서 빨강색으로 표시된 '3'이 동일해야만 곱셈이 성립 가능하다.

   또한, (3x4) * (4x5) 에서도 빨강색으로 표시된 '4'가 동일해야만 곱셈이 성립 가능하다.

   즉, 순서가 (2x3) * (3x4) * (4x5) 이렇게 1개만 존재한다는 것인데 이를 찾는 것이다.

   순서를 찾는 과정은 단순 반복문을 통해서 모든 경우를 다 비교해서 찾아주었다.

   말로 설명이 어려워서 코드를 보면서 이해해보자. 

void Make_Matrix_Order()
{
    for (int i = 0; i < M_Idx; i++)
    {
        R_Matrix[0].first = Matrix[i].first;
        R_Matrix[0].second = Matrix[i].second;
 
        int Idx = 1;
        int Cur_Col = R_Matrix[0].second;
 
        for (int j = 0; j < M_Idx - 1; j++)
        {
            bool Flag = false;
            for (int k = 0; k < M_Idx; k++)
            {
                if (Matrix[k].first == Cur_Col)
                {
                    R_Matrix[Idx].first = Matrix[k].first;
                    R_Matrix[Idx].second = Matrix[k].second;
                    Cur_Col = R_Matrix[Idx].second;
                    Idx++;
                    Flag = true;
                }
            }
            if (Flag == false) break;
        }
        if (Idx == M_Idx) break;
    }
}

    이것이 본인이 구현한 행렬의 순서를 찾는 코드이다.

    가장 먼저 모든 행렬을 반복하면서 시작점으로 가정해보고 시작한다. (line 3)

    행렬의 곱셈이 이루어지기 위해서는 A * B에서 A의 열과 B의 행이 같아야 하므로, A의 열을 저장하는 변수를

    선언 후, 이 변수와 값을 비교하면서 행렬을 찾아 간다. (line 9)

    이 후 과정은 반복문을 통해서 하나하나 모든 행렬을 순서대로 다 찾아보는 것이다.

    line by line으로 간략하게 설명을 하자면..

    line11 

    - 이미 1개의 행렬을 찾았다고 가정(line5 ~ 6에 의해서 첫번째 행렬을 임의로 가정하고 시작) 했으므로

      행렬이 총 M_Idx라고 했을 경우, M_Idx - 1 개 만큼 반복.

    line 14 ~ 24

    - 위에서 말했듯이, 미리 지정한 행렬의 열과 동일한 값을 갖는 행을 가진 행렬을 찾아가는 과정이다.

      만약, 동일한 행을 가진 행렬을 찾았다면, 그 다음 오는 행렬은 현재 찾은 행렬의 열이 되어야 하기 때문에

      line9 에서 선언해 놓은 변수 값도 재설정 해주면서 탐색을 반복한다.

    line 25

    - 이 경우에 걸리는 상황은, 처음에 설정한 '열'과 동일한 값을 갖는 '행'을 찾지 못했다는 의미이다.

      즉, line 5 ~ 6에서 가정한 첫 번째 행렬이 틀렸다는 이야기 이므로 그 다음 행렬을 다시 첫번째 행렬로

      설정하고 다시 탐색하게 하기 위한 break 문이다.

    line 27

    - 이 경우에 걸리는 상황은, 모든 행렬의 순서가 정해졌다는 것을 의미한다.

      행렬의 전체 갯수가 M_Idx개 인데, 어떠한 행렬을 시작값으로 가정해서 총 Idx개 만큼의 행렬을 탐색했다면

      이는 행렬의 순서를 찾았다는 의미이므로 걸어놓은 break 문이다.

2) 위와 같이 행렬의 순서를 찾았다. 그럼 이제 곱하기만 하면 되는데 중요한 건 곱하기의 최소횟수를 구해야 하는 것이다.

   2x3 , 3x4 , 4x5 짜리 행렬 3개가 있다고 가정해보자. 사실 { (2x3)*(3x4) } * (4x5) 를 하든, (2x3) * { (3x4)*(4x5) } 를

   하든 행렬에 들어가는 원소 값들의 결과는 같을 것이다. 하지만, 어떤 행렬을 먼저 계산 하냐에 따라서 연산횟수가

   달라지게 된다. 행렬의 곱의 연산 횟수는 '앞에 행렬의 행 x 앞에 행렬의 열 or 뒤에 행렬의 행 x 뒤에 행렬의 열' 이 된다.

   예를 들어서 (2x3) * (3x4) 를 하게 되면, 연산횟수는 2 x 3 x 4 = 24번이 된다.

   즉, 이렇게 계산을 해보면, { (2x3)*(3x4) } * (4x5) 의 경우에는

   { (2x3)*(3x4) } 에 의해서 24번의 연산 + { (2x4)*(4x5) } 에 의해서 40번의 연산 = 64번의 연산이 나오게 된다.

   윗 줄에서 갑자기 튀어나온 (2x4)는, 곱셈결과로 나온 행렬이다. { (2x3) * (3x4) } 를 계산하게 되면 (2x4)짜리 행렬이

   생성되어진다. { (axb)*(bxc) } = (a x c) 짜리 행렬.

   하지만, (2x3) * { (3x4)*(4x5) } 로 계산할 경우, { (3x4)*(4x5) } 에서 60번의 연산 + { (2x3) * (3x5) } 에 의해서

   30번의 연산 = 총 90번의 연산을 하게 된다.

   즉, 어떻게 계산하냐에 따라서 연산의 횟수가 달라지게 된다.

   이런 경우에 '연쇄행렬 최소곱셈' 알고리즘을 사용하게 되는데, 본인은 Dynamic Programming 방법과 재귀를 통해서

   구현해 보았다.

   본인은, 각 행렬 별 최소곱셈 수를 저장하기 위한 2차원 배열을 하나 선언해 주었다.

   int DP[][] 라는 배열을 선언해 주었는데, DP[a][b] = c의 의미는 "a번 행렬과 b번 행렬의 최소곱셈 횟수는 c번입니다."

   를 의미한다. 이 DP값을 채우기 위해서 재귀를 사용해주었는데, 재귀함수에 사용되는 매개변수는 2개가 있다.

   (int Left, int Right) 가 호출되어지는데, Left와 Right의 의미는 "Left번 행렬에서 Right번 행렬" 까지의 최소곱셈 횟수를

   구하기 위해서 호출된 함수(?) 라는 것을 의미한다.

   동작 과정을 간단하게 예시를 통해서 알아보자.

   A * B * C * D * E 이렇게 5개의 행렬의 최소곱셈 횟수를 알아본다고 생각해보자.

   우리는 괄호를 정말 여러 경우로 묶어볼 수 있다.

   가장 크게, A * { B * C * D * E } 이렇게 묶어볼 수도 있고, 혹은 { A * B } * { C * D * E } 뭐 이렇게도 묶어볼 수 있다.

   더 나아가서는 A * { (B * ( C * D ) * E }  뭐 이런식으로도 묶어볼 수 있을 것이다.

   이렇게 괄호를 묶는 경우를 위에서 말했듯이, 재귀 함수를 통해서 범위만 매개변수로 가지고 다니면서 계산을 해본 것이다.

   그럼 A * { B * C * D * E } 로 묶는 경우를 통해서 어떻게 동작하는지 알아보자.

   A * { B * C * D * E } 로 묶는 경우, 연산의 횟수는 어떻게 될까 ??

   아마, ' A의 행 * { B * C * D * E } 에서 계산된 최소 연산 횟수로 의해 생성된 행렬의 행 or A의 열 *

   { B * C * D * E } 에서 계산된 최소 연산 횟수로 의해 생성된 행렬의 열 ' 이 될 것이다.

   말이 조금 이상할지 몰라도 하나하나 천천히 읽어보면 맞는 말이다..

   본인이 재귀를 사용한 이유를 위에서 찾아볼 수 있다. 바로 "{B * C * D * E } 에서 계산된 최소 연산 횟수로 의해 생성된

   행렬" 이라는 말 때문이다.

   { B * C* D * E } 도 수많은 괄호로 묶일 수가 있다. { B * (C * D) * E }가 있을수도 있고, { (B * C) * D * E } 가 있을 수도

   있고....

   말로는 설명이 너무 어려우니 코드를 보면서 이해해보자.

int Calculate_Matrix(int Left, int Right)
{
    if (Left == Right) return 0;
    if (DP[Left][Right] != -1) return DP[Left][Right];
    
    int Temp_Result = INF;
    for (int i = Left; i < Right; i++)
    {
        int T_Result1 = Calculate_Matrix(Left, i);
        int T_Result2 = Calculate_Matrix(i + 1, Right);
        int Calculate_Num = R_Matrix[Left].first * R_Matrix[i].second * R_Matrix[Right].second;
 
        Temp_Result = Min(Temp_Result, T_Result1 + T_Result2 + Calculate_Num);
    }
 
    DP[Left][Right] = Temp_Result;
    return Temp_Result;
}
 

    본인의 코드이다. 라인별로 하나씩 알아가보자.

    위에서 부터 이어지게, A * B * C * D * E 에서 최소 연산 횟수를 구하는 상황으로 설명을 진행해 보겠다..

    가장 먼저, Calculate_Matrix함수는 (0, 4)로 호출이 되었다. A = 0 ~ ... ~ E = 4 이기 때문에 !

    line7 번을 보게 되면, Left부터 Right 까지 반복을 하게 되는데, 이 부분이 괄호를 묶는 부분을 나타낸다.

    line 9, 10 에서 보면 2개의 함수가 호출이 되는데 , Left부터 i 까지, i + 1부터 Right 까지를 계산하게 된다.

    즉, A * B * C * D * E 에서 가장 처음 호출되어서 Left = 0, Right = 4 일 때, line 7의 i 는 처음에 0일 것이다. 그럼 이 때,

    "0번 행렬부터 0번 행렬까지의 최소 곱셈 횟수" , "1번 행렬부터 4번행렬까지의 곱셈횟수" 로 line 9 , 10이 호출될 것이다.

    그 안에서 재귀를 타고 들어가게되면 "0번행렬부터 0번행렬까지의 최소 곱셈 횟수"는 당연히 0번일 것이고,

    "1번 행렬부터 4번행렬까지의 곱셈횟수" 로 함수에 들어가 질 것이다.(Left = 1 / Right = 4)

    그럼 그 안에도 또 나뉘는 것이다. 즉, 위에서 말했뜻이 B * C * D * E 이 또한 여러개의 괄호로 묶일 수도 있으므로

    이 B * C * D * E를 여러 경우로 다 묶어보는 것이다.

    Left = 1 / Right = 4 일 경우,

    line9 에 의해서 (1, 1) 호출 = 0 return.

    line10 에 의해서 (2, 4) 호출

    (2 , 4)가 호출되었다 라는 것은 ? C * D * E 를 또 묶어보겠다는 것이다. 왜냐하면 C * D * E 도 어떻게 묶는지에 따라서

    연산 횟수가 달라지므로 !

    이런식으로 재귀를 쭉쭉 타고 들어가는 것이다. 위에서 약간 복잡한 내용을 말했는데, 위에 내용은 가장 처음 (0, 4)로

    호출되었을 때, i = 0 일때만 이야기를 한 것이다. i 는 계속 증가하면서 반복할 것이고, 그에 따라서 괄호를 어떻게 치는지에

    따라서 최소 연산 횟수가 계산될 것이다.

 

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
#define INF 987654321
#define MAX 110
#define endl "\n"
using namespace std;
 
int N, Answer, M_Idx;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
int DP[25][25];
pair<int, int> Matrix[25], R_Matrix[25];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    M_Idx = 0;
    memset(Visit, false, sizeof(Visit));
    memset(DP, -1, sizeof(DP));
    Answer = 987654321;
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] != 0 && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Count_Size(int x, int y)
{
    int Tx = x;
    int Ty = y;
    int Row = 0;
    int Col = 0;
 
    while (1)
    {
        if (Tx >= N) break;
        if (MAP[Tx][y] == 0) break;
        Tx++;
        Row++;
    }
    while (1)
    {
        if (Ty >= N) break;
        if (MAP[x][Ty] == 0) break;
        Ty++;
        Col++;
    }
    Matrix[M_Idx].first = Row;
    Matrix[M_Idx++].second = Col;
}
 
void Make_Matrix_Order()
{
    for (int i = 0; i < M_Idx; i++)
    {
        R_Matrix[0].first = Matrix[i].first;
        R_Matrix[0].second = Matrix[i].second;
 
        int Idx = 1;
        int Cur_Col = R_Matrix[0].second;
 
        for (int j = 0; j < M_Idx - 1; j++)
        {
            bool Flag = false;
            for (int k = 0; k < M_Idx; k++)
            {
                if (Matrix[k].first == Cur_Col)
                {
                    R_Matrix[Idx].first = Matrix[k].first;
                    R_Matrix[Idx].second = Matrix[k].second;
                    Cur_Col = R_Matrix[Idx].second;
                    Idx++;
                    Flag = true;
                }
            }
            if (Flag == false) break;
        }
        if (Idx == M_Idx) break;
    }
}
 
int Calculate_Matrix(int Left, int Right)
{
    if (Left == Right) return 0;
    if (DP[Left][Right] != -1) return DP[Left][Right];
    
    int Temp_Result = INF;
    for (int i = Left; i < Right; i++)
    {
        int T_Result1 = Calculate_Matrix(Left, i);
        int T_Result2 = Calculate_Matrix(i + 1, Right);
        int Calculate_Num = R_Matrix[Left].first * R_Matrix[i].second * R_Matrix[Right].second;
 
        Temp_Result = Min(Temp_Result, T_Result1 + T_Result2 + Calculate_Num);
    }
 
    DP[Left][Right] = Temp_Result;
    return Temp_Result;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] != 0 && Visit[i][j] == false)
            {
                BFS(i, j);
                Count_Size(i, j);
            }
        }
    }
 
    Make_Matrix_Order();
    Answer = Calculate_Matrix(0, M_Idx - 1);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}