[ 백준 20058 ] 마법사 상어와 파이어스톰 (C++)

백준의 마법사 상어와 파이어스톰(20058) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

문제를 단계별로 나눠서 해당 단계별로 풀이과정을 알아보고, 정답을 도출하는 과정까지 진행해보자.

#1. 맵 회전하기

이 문제에서 가장 핵심적인 부분이자, 가장 어려움을 느낄만한 부분이라고 생각한다.

사실 이후에 있는 얼음의 가장 큰 덩어리를 구하는 탐색 과정도 굉장히 간단한 탐색과정이라서 본인은 이 맵을 회전시키는 부분이 가장 핵심이라고 생각한다.

( 이렇게 주어진 배열을 회전시키는 과정 혹은 배열의 인덱스를 가지고 장난을 쳐야하는 이런 과정은 항상 말하지만 본인이 가장

  이해하기 쉽고 구현하기 쉬운 방법이 정답이라고 생각합니다. 이 글에서는 제가 주로 사용하는 방법에 대해서 이야기

  하겠습니다. )

다음과 같은 3개의 맵을 가지고 진행을 해볼 것이다.

가장 왼쪽에 있는 맵부터 1번, 2번, 3번 맵이라고 번호를 붙여서 표현하겠다.

1번맵은 한 변의 길이가 2인 사각형이고, 2번맵은 한 변의 길이가 4, 3번 맵은 한 변의 길이가 6인 사각형이다.

지금부터는 위의 1번, 2번, 3번맵을 회전 시키는 과정을 진행하겠다.

#1 - 1) 1단계 : 돌려야 하는 사각형의 갯수 구하기

본인은 위와 같은 맵을 회전시킬 때, 가장 먼저 판단하는 것이 "돌려야 하는 사각형의 갯수" 이다.

이게 무슨말일까??

먼저, 1번맵에는 돌려야 하는 사각형의 갯수가 1개가 있다.

.

바로 이렇게 빨강색 사각형만 돌려주면 된다.

하지만, 2번맵 같은 경우에는 사각형의 갯수가 2개가 있다.

.

바로 위와 같이, 빨강색으로 칠해진 사각형들에 대해서 회전이 일어나야하고, 파랑색으로 칠해진 사각형들에 대해서 회전이 일어나야 한다. 회전하는 과정에서 서로 다른 두 색깔의 영향을 받는 경우는 존재하지 않는다.

3번맵 같은 경우에는 사각형의 갯수가 3개가 있다.

.

위와 같이 3개의 사각형을 돌려주어야 한다.

본인은, 이렇게 사각형들을 다 나눈 후에, 색깔별로 따로따로 회전시키는 과정을 진행할 것이다.

그럼 ! 현재 주어진 범위에서 사각형이 몇 개가 있는지는 어떻게 판단을 해줘야 할까 ??

1번맵은 길이가 '2'인 사각형이였고, 돌려야 하는 사각형의 갯수가 1개였다.

2번맵은 길이가 '4'인 사각형이였고, 돌려야 하는 사각형의 갯수가 2개였다.

3번맵은 길이가 '6'인 사각형이였고, 돌려야 하는 사각형의 갯수가 3개였다.

길이가 'Len'인 사각형은 돌려야 하는 사각형의 갯수가 몇 개 일까?? 바로 "Len / 2" 개가 된다.

따라서 본인은 가장 먼저 ! 주어진 사각형의 길이를 통해서 돌려야 하는 사각형의 갯수를 파악해 주었다.

# 돌려야 하는 사각형의 갯수 = 주어진 사각형의 길이 / 2 개.

#1 - 2) 2단계 : 기준점 설정

3번 맵을 한번 살펴보자.
.

1단계에서 했던 이야기로 미뤄본다면, 각각의 색깔이 칠해진 사각형들을 독립적으로 회전을 시켜야 하는데, 각각의 색깔을 가진 사각형들은 모두 길이도 다르고 가지고 있는 데이터의 갯수 또한 다르다. 어떻게 독립적으로 돌릴 수 있을까 ??

본인은 각각의 사각형들에 대한 "기준점"을 통해서 이를 해결한다.

기준점은 2개의 좌표를 의미한다. 바로 "가장 왼쪽 위의 좌표와 가장 오른쪽 아래의 좌표" 이다.

3번 맵에서의 기준점들을 찾아보자. (주어진 맵에서 가장 왼쪽 위의 좌표는 (1 , 1) 이라고 가정하겠습니다.)

빨강색 사각형에서 가장 왼쪽 위의 좌표는 (1 , 1)이고 가장 오른쪽 아래의 좌표는 (6 , 6) 이다.

파랑색 사각형에서 가장 왼쪽 위의 좌표는 (2 , 2)이고 가장 오른쪽 아래의 좌표는 (5 , 5) 이다.

노랑색 사각형에서 가장 왼쪽 위의 좌표는 (3 , 3)이고 가장 오른쪽 아래의 좌표는 (4 , 4) 이다.

그럼 저 좌표들을 어떻게 구해야할까 ?? 일단 시작점은 (1 , 1)이 될 것이다. 그리고 위의 사각형들을 가장 큰 사각형부터

0번, 1번, 2번으로 번호를 붙이는 것이다. 빨강색 사각형은 0번사각형, 파랑색은 1번, 노랑색은 2번 사각형이 되는 것이다. 그럼 위의 좌표들은 다음과 같이 나타낼 수 있다.

각각의 사각형에서의 가장 왼쪽 위의 좌표 = (시작 x좌표 + 사각형의 번호 , 시작 y좌표 + 사각형의 번호)

각각의 사각형에서의 가장 오른쪽 아래의 좌표 =

(시작 x좌표 + 길이 - 사각형의 번호 - 1 , 시작 y좌표 + 길이 - 사각형의 번호 - 1)

갑자기 이상한 식들이 많이 나왔다. 한번 직접 확인해보자.

빨강색 사각형에서의 가장 왼쪽 위의 x좌표 = 시작점 x좌표인 '1' + 사각형의 번호 '0' = 1

빨강색 사각형에서의 가장 왼쪽 위의 y좌표 = 시작점 y좌표인 '1' + 사각형의 번호 '0' = 1

빨강색 사각형에서의 가장 오른쪽 아래의 x좌표 = 시작점 x좌표인 '1' + 맵의 길이인 '6' - 사각형의 번호인 '0' - 1 = 6

빨강색 사각형에서의 가장 오른쪽 아래의 y좌표 = 시작점 y좌표인 '1' + 맵의 길이인 '6' - 사각형의 번호인 '0' - 1 = 6

파랑색 사각형에서의 가장 왼쪽 위의 x좌표 = 시작점 x좌표인 '1' + 사각형의 번호 '1' = 2

파랑색 사각형에서의 가장 왼쪽 위의 y좌표 = 시작점 y좌표인 '1' + 사각형의 번호 '1' = 2

파랑색 사각형에서의 가장 오른쪽 아래의 x좌표 = 시작점 x좌표인 '1' + 맵의 길이 '6' - 사각형의 번호 '1' - 1 = 5

파랑색 사각형에서의 가장 오른쪽 아래의 y좌표 = 시작점 y좌표인 '1' + 맵의 길이 '6' - 사각형의 번호 '1' - 1 = 5

노랑색 사각형은 직접 해보길 바란다. 해보더라도 위의 식대로 그대로 나온다는 것을 확인할 수 있을 것이다.

조금은 복잡해보이지만, 이런 과정을 통해서 본인은 각각의 사각형들의 기준점을 만들어 준다.

그럼 이 기준점들을 어떻게 해서 설정했다고 생각해보자.

이 기준점들을 가지고 뭘 어떻게 사각형을 회전 시킬 수 있을까 ??

기준점이 만약 (1 , 1)과 (6 , 6)이 나왔다고 가정해보자. 그럼 우리는 이를 통해서 다음과 같은 사실을 알 수 있는 것이다.

1. 1행에서 1열 ~ 6열에 해당하는 값들을 바꿔줘야 겠다.

2. 1열에서 1행 ~ 6행에 해당하는 값들을 바꿔줘야 겠다.

3. 6행에서 1열 ~ 6열에 해당하는 값들을 바꿔줘야 겠다.

4. 6열에서 1행 ~ 6행에 해당하는 값들을 바꿔줘야 겠다.

우리는 위와 같이 우리가 회전해야 할 범위에 대해서 알 수 있는 것이다.

즉, 기준점이 만약 (x , y)와 (xx , yy)가 나왔다고 가정해보자. 그럼 우리는 이를 통해서 다음에 속하는 범위에 있는 값들을 손대야 한다는 것을 알 수 있다.

1. x행에서 y열 ~ yy열에 해당하는 값들을 바꿔줘야 겠다.

2. y열에서 x행 ~ xx행에 해당하는 값들을 바꿔줘야 겠다.

3. xx행에서 y열 ~ yy열에 해당하는 값들을 바꿔줘야 겠다.

4. yy열에서 x행 ~ xx행에 해당하는 값들을 바꿔줘야 겠다.

즉 ! 우리는 이와 같이 구한 2개의 기준점을 통해서 우리가 회전시켜야 하는 사각형들이 어느 범위에 있는 값들인지를 그 범위를 추론할 수 있게 된다.

1. 주어진 범위에서, 돌려야 하는 사각형의 갯수를 구해준다. (#1 - 1의 과정)

2. 돌려야 하는 각각의 사각형은 각각 모두 다른 범위를 가지고 있다.

3. 이 범위를 판단하기 위해서 우선적으로 '기준점' 2개를 파악한다.

4. 기준점 2개는 "가장 왼쪽 위의 좌표" 와 "가장 오른쪽 아래의 좌표" 가 된다.

5. 이 기준점을 구하는 과정에서 반드시 필요한 요소가 "사각형의 번호" 이다.

6. 기준점 2개를 통해서 우리는 어디의 값들을 변경시켜줘야 할지 그 범위에 대해서 파악할 수 있다.

#1 - 3) 회전 시키기

지금부터는 본격적으로 회전시키는 과정을 진행할 것이다.

다음과 같은 맵으로 진행해보자.

.

위의 맵에서 가장 큰 사각형인 색깔이 칠해져 있는 부분에 대해서 시계방향으로 회전을 시킨다고 가정해보자.

지금부터 위의 맵에서 빨강색으로 칠해진 부분을 'A번' , 노랑색은 'B번', 파랑색은 'C번', 초록색은 'D번' 이라고 표현하겠다.

회전시키는 과정은 다음과 같다.

1. A번 줄을 임시의 저장공간에 복사를 해놓는다.

2. 노랑색 줄을 빨강색 줄에 복사한다.

3. 파랑색 줄을 노랑색 줄에 복사한다.

4. 초록색 줄을 파랑색 줄에 복사한다.

5. 1번 과정에서 저장해놓은 데이터를 초록색 줄에 복사한다.

이렇게 5가지 과정을 진행해 주면 된다.

그럼 각 과정에 대해서 조금만 더 깊이 있게 알아보자. 지금부터 기준점 2개를 구했더니 (Sx, Sy), (Ex, Ey)가 나왔다고 가정해 보겠다.

1. A번 줄을 임시의 저장 공간에 복사를 해놓는다.

- 저 데이터들은 어디에 해당하는 값들일까 ?? 바로 (Sx , Sy) ~ (Ex - 1 , Sy) 에 해당하는 값들이다.

  즉, Sx ~ Ex - 1까지 반복하면서, (Sx ~ Ex - 1 , Sy) 에 해당하는 값들을 임시의 저장공간에 복사를 해주면 된다.

2. 노랑색 줄을 빨강색 줄에 복사한다.

- 이제부터 계속해서 무조건 기준점을 이용해서 해당 줄이 어디에 해당하는 범위인지만 생각을 하면 된다.

  빨강색 줄의 범위 : (Sx , Sy) ~ (Ex - 1 , Sy)

  노랑색 줄의 범위 : (Ex , Sy) ~ (Ex , Ey - 1)

  즉 , Sx ~ Ex - 1까지 반복하면서 (Sx ~ Ex - 1 , Sy) 에 해당하는 값들에다가 (Ex , Sy ~ Ey - 1)에 해당하는 값들을

  덮어 쓰면 된다.

3. 파랑색 줄을 노랑색 줄에 복사한다.

- 노랑색 줄의 범위 : (Ex , Sy) ~ (Ex , Ey - 1)

  파랑색 줄의 범위 : (Ex , Ey) ~ (Sx + 1 , Ey)

  즉, Sy ~ Ey - 1 까지 반복하면서 (Ex , Sy ~ Ey - 1) 에 해당하는 값들에다가 (Ex ~ Sx + 1 , Ey) 에 해당하는 값들을

  덮어 쓰면 된다.

4. 초록색 줄을 파랑색 줄에 복사한다.

- 파랑색 줄의 범위 : (Ex , Ey) ~ (Sx + 1 , Ey)

  초록색 줄의 범위 : (Sx , Sy + 1) ~ (Sx , Ey)

  즉, Ex ~ Sx + 1 까지 반복하면서 (Ex ~ Sx + 1 , Ey)에 해당하는 값들에다가 (Sx , Sy + 1 ~ Ey) 에 해당하는 값들을

  덮어 쓰면 된다.

그럼 여기까지 진행했을 때, 어떤 상태가 되어있을까 ??

.

이렇게 되어 있을 것이다. 이 상태에서 마지막에 빨강색 줄을 초록색 줄에 복사한다면 ???

정말로 이상한 상황이 발생하게 될 것이다. 그래서 ! 우리는 1번 과정에서 빨강색 줄을 미리 복사해둔 것이다.

그 복사해둔 것을 초록색 칸에 채워주면...

.

이렇게 정상적으로 회전했다는 것을 알 수 있다.

지금까지 도형을 회전하는 과정에 대해서 굉장히 구체적으로 조금 이야기를 해봤는데....

사실, 기준점만 설정한다면, 실제로 돌리는 과정을 구현해보면, 지금 이 글을 읽을 때 보다 훨씬 더 쉬운 과정이라는 것을

느낄 것이다. 본인도 문제를 풀 때에는 별로 안 헷갈렸는데 이렇게 글로 쓰다보니까 너무나도 많이 헷갈렸다.

위에서도 이야기 했지만, 본인이 가장 선호하는 방법을 이야기한 것일 뿐, 특별한 알고리즘, 특별한 방법, 특별한 자료구조가 사용된 것이 아니기 때문에 각자가 선호하고 이해하기 쉬운 풀이가 최고의 풀이라고 생각한다.

위의 과정을 소스코드로 나타낸 것이다.

void Turning(int a, int b, int Len)
{
    int Square = Len / 2;
    for (int Number = 0; Number < Square; Number++)
    {
        int Start_x = a + Number;
        int Start_y = b + Number;
        int End_x = a + Len - Number - 1;
        int End_y = b + Len - Number - 1;
 
        int x_Idx = End_x;
        int y_Idx = Start_y;
        int Idx = 0;
        vector<int> Temp;
        for (int i = Start_x; i < End_x; i++) Temp.push_back(MAP[i][Start_y]);
        for (int i = Start_x; i < End_x; i++) MAP[i][Start_y] = MAP[End_x][y_Idx++];
        for (int i = Start_y; i < End_y; i++) MAP[End_x][i] = MAP[x_Idx--][End_y];
        for (int i = End_x; i > Start_x; i--) MAP[i][End_y] = MAP[Start_x][y_Idx--];
        for (int i = End_y; i > Start_y; i--) MAP[Start_x][i] = Temp[Idx++];
    }
}

line3) 사각형의 갯수를 구하는 과정이다.

line4) 사각형의 번호를 가장 큰 사각형을 0번으로부터해서 번호를 붙여주고, 해당 사각형들의 갯수만큼 반복해준다.

line6 ~ 9) 기준점을 설정하는 부분이다.

line15 ~ 19) 회전하는 1 ~ 5 단계에 대한 반복문 들이다. line15부터 순차적으로 1단계, 2단계.. 5단계 이다.

#2. 얼음 녹이기

이제 어려운 과정은 다 끝났다. 얼음을 녹이는 과정은, 얼음이 있는 칸(MAP에서 0이 아닌 칸)에서 상하좌우 4방향을

탐색한 후에, 정상적인 얼음이 있는 곳이 3군데 미만이라면 그 칸의 얼음을 감소시켜 주면 된다.

#3. 가장 큰 덩어리 구하기

본인은 이 부분을 완전탐색으로, 그 중에서도 너비우선탐색인 BFS탐색을 통해서 구현해 주었다.

맵의 모든 좌표를 탐색하면서, BFS탐색을 해볼만한 좌표들에 대해서만 탐색을 해 주었다.

해볼만한 좌표라는 것은, "얼음이 0이 아닌 좌표" 이고 "아직 탐색하지 않은 좌표" 를 의미한다.

기존에 이미 탐색을 한번 했던 좌표라면, 해당 좌표에서 탐색을 다시하더라도 기존에 탐색을 했던 범위와 똑같이 탐색을 할 것이기 때문에 불필요한 탐색이 된다.

따라서 아직 탐색을 하지 않았으면서, 얼음의 양이 0이 아닌 좌표에 대해서만 BFS 탐색을 통해서 진행해 주었다.

#4. 정답도출

가장 큰 덩어리는 #3의 과정에서 구할 수 있다.

남아있는 얼음의 합을 구하기 위해서 본인은 가장 처음에 입력과 동시에 모든 맵에 있는 얼음의 총합을 구해놓았다.

그리고 #2의 과정에서 얼음이 녹을 때 마다, 얼음의 총합에서도 -- 시켜주었다.

[ 소스코드 ]

#include <iostream>
#include <vector>
#include <queue>
 
#define MAX 70
#define endl "\n"
using namespace std;
 
int N, Q, Sum_Answer, Size_Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
vector<int> Cmd;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Max(int A, int B) { return A > B ? A : B; }
 
void Input()
{
    cin >> N >> Q;
    N = (1 << N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            Sum_Answer += MAP[i][j];
        }
    }
    for (int i = 0; i < Q; i++)
    {
        int a; cin >> a;
        Cmd.push_back(a);
    }
}
 
void Turning(int a, int b, int Len)
{
    int Square = Len / 2;
    for (int Number = 0; Number < Square; Number++)
    {
        int Start_x = a + Number;
        int Start_y = b + Number;
        int End_x = a + Len - Number - 1;
        int End_y = b + Len - Number - 1;
 
        int x_Idx = End_x;
        int y_Idx = Start_y;
        int Idx = 0;
        vector<int> Temp;
        for (int i = Start_x; i < End_x; i++) Temp.push_back(MAP[i][Start_y]);
        for (int i = Start_x; i < End_x; i++) MAP[i][Start_y] = MAP[End_x][y_Idx++];
        for (int i = Start_y; i < End_y; i++) MAP[End_x][i] = MAP[x_Idx--][End_y];
        for (int i = End_x; i > Start_x; i--) MAP[i][End_y] = MAP[Start_x][y_Idx--];
        for (int i = End_y; i > Start_y; i--) MAP[Start_x][i] = Temp[Idx++];
    }
}
 
void Remake_MAP(int Len)
{
    for (int i = 0; i < N; i += Len)
    {
        for (int j = 0; j < N; j += Len)
        {
            Turning(i, j, Len);
        }
    }
}
 
void Melting_Ice()
{
    vector<pair<int, int>> V;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == 0) continue;
 
            int Cnt = 0;
            for (int k = 0; k < 4; k++)
            {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (MAP[nx][ny] == 0) continue;
                Cnt++;
            }
 
            if (Cnt < 3) V.push_back(make_pair(i, j));
        }
    }
 
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
        MAP[x][y]--;
        Sum_Answer--;
    }
}
 
int BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
    int Cnt = 1;
 
    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));
                    Cnt++;
                }
            }
        }
    }
    return Cnt;
}
 
void Calculate_Ice_Size()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == 0) continue;
            if (Visit[i][j] == true) continue;
            
            int Result = BFS(i, j);
            Size_Answer = Max(Size_Answer, Result);
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < Q; i++)
    {
        int L = (1 << Cmd[i]);
        Remake_MAP(L);
        Melting_Ice();
    }
    Calculate_Ice_Size();
 
    cout << Sum_Answer << endl << Size_Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}