[ 백준 21610 ] 마법사 상어와 비바라기 (C++)

백준의 마법사 상어와 비바라기(21610) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 조건에 맞게 구름을 이동시키고, 바구니에 물을 채우고 등의 상황을 진행했을 때, 최종적으로 남아있는 바구니에 담긴 물의 양의 총합을 구해야 하는 문제이다.

문제 해결을 위해 필요한 정보를 관리하는 방법부터 정답을 도출하는 과정까지 진행해보자.

 

#1. 구름의 관리

먼저, 문제의 핵심인 구름을 관리하는 방법부터 알아보도록 하자.

본인은 구름을 2가지 자료형을 이용해서 관리해 주었다.

1. 2차원 배열을 통해서, 구름이 있는 좌표를 표시

2. Vector를 통해서, 구름이 있는 좌표를 저장

위와 같이 2가지 방법 모두를 이용해서 구름을 관리해 주었다.

왜 2가지나 필요한지, 어느 한 가지 방법만 사용하면 안되는지 와 같은 이야기는 아래에서 이 다음 단계들을 진행하면서 순차적으로 알아보자.

다음 코드는 구름을 관리하기 위한 변수들을 선언하는 과정과 구름의 초기설정 과정이다.

bool Cloud_MAP[MAX][MAX];
vector<pair<int, int>> Cloud;

void Init_Cloud()
{
	Cloud.push_back(make_pair(N - 2, 0));
	Cloud.push_back(make_pair(N - 2, 1));
	Cloud.push_back(make_pair(N - 1, 0));
	Cloud.push_back(make_pair(N - 1, 1));
	Cloud_MAP[N - 2][0] = true;
	Cloud_MAP[N - 2][1] = true;
	Cloud_MAP[N - 1][0] = true;
	Cloud_MAP[N - 1][1] = true;
}

위와 같이 2가지 방법으로 선언해 주었다.

Cloud_MAP이라는 2차원 배열은 "구름이 있는 곳을 true로 표시" 해주는 역할이다.

예를 들어서 Cloud_MAP[A][B] = true 라는 것은 (A , B)는 현재 구름이 있습니다 를 의미한다.

vector<pair<int, int>> Cloud 에는 "구름이 있는 곳의 좌표들을 저장" 해주는 역할이다.

# 구름을 관리하기 위해서 2가지 방법으로 선언해 주었다.
# 1. 2차원 배열로 만들어서 구름이 있는 좌표를 확인할 수 있다.
# 2. vector로 만들어서 구름의 좌표 정보를 저장해 놓는다.

 

#2. 구름 이동하기

구름을 이동하는 과정을 진행할 때에는 구름이 있는 위치에서 칸 수 만큼 움직이는 방향으로 옮겨주면 된다.

그런데 ! 여기서 골치 아픈 과정이 하나 있다. 바로 "맵은 처음과 끝이 연결되어 있다" 라는 것이다.

더 나아가, 맵의 동/서/남/북 중 어느 한 방향으로 나가는 것은 쉽게 바꿀 수 있지만, 대각선으로 맵의 범위를 벗어나는 과정은 본인에게 있어서 조금 어려운 과정이었다. 지금부터는 이 과정을 본인이 해결한 굉장히 쉬운 방법을 소개하겠다.

정말 간단하게 좌표의 개념 (x , y)의 개념으로 접근하는 것이 아닌, x좌표와 y좌표를 따로따로 생각해 버리면 쉽다.

x좌표가 범위 밖으로 나가게 되면, x좌표를 범위 내로 넣어주면 되고, y좌표가 범위 밖으로 나가게 되면, y좌표를 범위 내로 넣어주면 된다.

본인은, 처음에 (x , y)를 쌍으로 관리하려다 보니 조금 혼란스러운 부분이 있었는데, 위와 같은 방법으로 해결하였다.

그리고 ! 여기서 #1에서 선언한 구름을 관리하기 위한 변수 'Vector'를 사용할 것이다.

왜냐하면, 구름을 관리하기 위한 변수 중, 2차원 배열로 이 과정을 진행한다고 가정해보면, 모든 맵을 탐색하면서 구름이 있는 곳을 찾은 후에 구름을 옮기는 과정을 진행해 주어야 한다.

하지만 ! Vector에 "현재 구름이 있는 좌표 정보"들을 저장해 놨으므로, 모든 맵을 탐색할 필요 없이 바로바로 구름의 좌표 정보에 직접적으로 접근이 가능하다.

void Move_Cloud(int Idx)
{
	int Dir = Cmd[Idx].first;
	int Cnt = Cmd[Idx].second;
	memset(Cloud_MAP, false, sizeof(Cloud_MAP));
	for (int i = 0; i < Cloud.size(); i++)
	{
		int x = Cloud[i].first;
		int y = Cloud[i].second;
		int nx = x;
		int ny = y;
		for (int j = 0; j < Cnt; j++)
		{
			nx += dx[Dir];
			ny += dy[Dir];
			nx = Make_Range(nx);
			ny = Make_Range(ny);
		}
		Cloud[i].first = nx;
		Cloud[i].second = ny;
	}
	for (int i = 0; i < Cloud.size(); i++)
	{
		int x = Cloud[i].first;
		int y = Cloud[i].second;
		Cloud_MAP[x][y] = true;
	}
}

 

#3. 구름이 있는 칸에 비가 내려 해당 칸의 물의 양이 1 증가

이 과정 또한 #1에 있는 vector를 이용해서 쉽게 진행할 수 있다.

여기서, #1에 있는 2차원 배열을 이용해서 진행하려면, 모든 맵을 다 탐색하면서 구름이 있는 칸을 찾아야 하는 과정이 필요한데, vector를 이용한다면 "구름이 있는 좌표 정보"에 직접적으로 접근할 수 있다.

void Make_Rain()
{
	for (int i = 0; i < Cloud.size(); i++)
	{
		int x = Cloud[i].first;
		int y = Cloud[i].second;
		MAP[x][y]++;
	}
}

 

#4. 구름이 모두 사라진다 & 물복사버그 마법 시전

문제에서 주어진 순서 상으로는, 구름이 모두 사라진 후에, 가장 최근에 구름이 있었던 좌표들에 물복사버그 마법이 일어나는 것으로 되어있다. 하지만 본인은 구름이 모두 사라지는 과정을 진행하기 전에, 물 복사 버그 마법을 시전하는 것을 먼저 진행해 주었다. 지금부터 그 이유를 알아보기 전에, 사실 위의 두 개의 과정은 구현면에서 보면 굉장히 간단하니, 이를 구현하는 것 보다는 왜 순서를 바꿔주는 것이 더 편한지, 이를 통해서 어떤 과정을 더 편하게 접근할 수 있는지에 초점을 맞춰서 이야기 하겠다.

 

"구름이 모두 사라진다" 라는 것을 지금까지 우리가 진행한 과정으로 본다면, 어떤 과정을 진행하게 될까 ?? 아마,

1. 구름에 대한 좌표정보가 저장되어 있는 vector를 clear() 시키기

2. 구름이 있는 곳을 표시해놓은 2차원 배열을 모두 false로 초기화 시켜주기

위와 같이 2가지 과정을 진행하게 될 것이다. 그렇게 된다면, 물 복사 버그 마법을 시전하는 과정에서 필요한 "가장 최근에 구름이 있었던 좌표"에 대한 정보를 찾기가 너무 어려워 진다. 사실상 알 수 있는 방법이 없다.

따라서, 구름을 모두 사라지게 하는 과정 전에 "가장 최근에 구름이 있었던 좌표" 정보가 저장되어 있는 vector를 이용해서 물 복사 버그 마법을 시전해 주는 것이다.

이 마법을 시전 한 후에, 구름이 모두 사라지는 과정을 진행해 줄 것이다.

그런데 본인은 구름이 모두 사라지는 과정을 진행할 때에도 위에서 이야기한 2가지 과정을 모두 진행해 주지 않았다.

대신, vector에 들어있는 정보들만 모두 삭제해 주었다. 그렇게 되면 현재 어떤 상황이 될까 ??

#1에서 구름을 관리하기 위해서 "구름이 현재 있는 좌표"를 저장해 놓은 vector에는 아무런 데이터가 없을 것이지만,

#1에서 구름을 관리하기 위해서 선언해 놓은 2차원 배열에는 "가장 최근에 있었던 구름의 위치가 true로 표시" 되어 있는 상태일 것이다. 그럼 이 2차원 배열은, 구름이 모두 사라지는 과정을 진행함에도 불구하고 왜 살려놓는지 이 다음 과정에서 알아보자. 이부분에 대한 코드는 다음과 같다.

void Water_Bug()
{
	for (int i = 0; i < Cloud.size(); i++)
	{
		int x = Cloud[i].first;
		int y = Cloud[i].second;
		int Cnt = 0;
		for (int j = 2; j <= 8; j += 2)
		{
			int nx = x + dx[j];
			int ny = y + dy[j];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
			if (MAP[nx][ny] >= 1) Cnt++;
		}
		MAP[x][y] += Cnt;
	}
}

void Delete_Cloud()
{
	Cloud.clear();
}

 

#5. 물의 양이 2이상인 칸에 구름이 생기고 물의양이 2감소

지금부터 모든 맵을 탐색하면서, 물의 양이 2이상인 곳을 찾아서 그 곳에 구름을 생기게 할 것이고, 물의 양을 2 감소시킬 것이다. 그런데 ! 중요한 조건이 하나 있다.

바로 "#4의 과정에서 구름이 사라진 좌표에는 구름이 생기지 않는다" 는 것이다.

다시 이야기 해서, "구름이 사라지기 직전, 가장 최근에 구름이 있었던 좌표에 대해서는 이 과정이 적용되질 않는다" 라는 것이다. 바로 이게 우리가 #4에서 구름을 모두 사라지게 하는 과정을 진행할 때, 구름의 위치를 표시한 2차원 배열을 false로 초기화 시키지 않은 이유이다. 또한, 처음 #1에서 구름의 위치를 표현하기 위해서 2차원 배열을 선언한 이유이기도 하다.

모든 좌표를 탐색하면서, "물의 양이 2 이상이면서, 가장 최근에 구름이 있었던 좌표가 아닌 좌표" 를 찾아야 하는데, 이 과정을 #1에서 선언해 놓은 vector를 이용해서 진행한다고 가정해보자.

그렇다면, 맵을 탐색하면서 좌표 하나하나를 만날 때마다, vector를 탐색하면서 vector에 들어있는 좌표가 맞는지 아닌지를 비교하고 탐색해야 할 것이다. 오히려 더 복잡해진다는 것을 알 수 있다.

따라서, 어차피 모든 맵을 탐색해야 한다면(물의 양이 2이상인 좌표를 찾아야 하므로) vector보다는 구름의 위치가 표시되어 있는 2차원 배열을 이용해서 접근하는 것이 더 편할 것이고, 이를 위해서 #4에서 구름이 사라지는 과정을 진행했음에도 불구하고 2차원 배열에는 "가장 최근에 구름이 있었던 위치"를 그대로 남겨 두었던 것이다.

이 과정을 코드로 나타내면 다음과 같다.

void Make_Cloud()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (Cloud_MAP[i][j] == true) continue;
			if (MAP[i][j] < 2) continue;
			MAP[i][j] -= 2;
			Cloud.push_back(make_pair(i, j));
		}
	}

	memset(Cloud_MAP, false, sizeof(Cloud_MAP));
	for (int i = 0; i < Cloud.size(); i++)
	{
		int x = Cloud[i].first;
		int y = Cloud[i].second;
		Cloud_MAP[x][y] = true;
	}
}

 

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <vector>
 
#define MAX 55
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
bool Cloud_MAP[MAX][MAX];
vector<pair<int, int>> Cloud;
vector<pair<int, int>> Cmd;
 
int dx[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int dy[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(a, b));
    }
}
 
void Init_Cloud()
{
    Cloud.push_back(make_pair(N - 2, 0));
    Cloud.push_back(make_pair(N - 2, 1));
    Cloud.push_back(make_pair(N - 1, 0));
    Cloud.push_back(make_pair(N - 1, 1));
    Cloud_MAP[N - 2][0] = true;
    Cloud_MAP[N - 2][1] = true;
    Cloud_MAP[N - 1][0] = true;
    Cloud_MAP[N - 1][1] = true;
}
 
int Make_Range(int x)
{
    if (x < 0) return N - 1;
    if (x >= N) return 0;
    return x;
}
 
void Move_Cloud(int Idx)
{
    int Dir = Cmd[Idx].first;
    int Cnt = Cmd[Idx].second;
    memset(Cloud_MAP, false, sizeof(Cloud_MAP));
    for (int i = 0; i < Cloud.size(); i++)
    {
        int x = Cloud[i].first;
        int y = Cloud[i].second;
        int nx = x;
        int ny = y;
        for (int j = 0; j < Cnt; j++)
        {
            nx += dx[Dir];
            ny += dy[Dir];
            nx = Make_Range(nx);
            ny = Make_Range(ny);
        }
        Cloud[i].first = nx;
        Cloud[i].second = ny;
    }
    for (int i = 0; i < Cloud.size(); i++)
    {
        int x = Cloud[i].first;
        int y = Cloud[i].second;
        Cloud_MAP[x][y] = true;
    }
}
 
void Make_Rain()
{
    for (int i = 0; i < Cloud.size(); i++)
    {
        int x = Cloud[i].first;
        int y = Cloud[i].second;
        MAP[x][y]++;
    }
}
 
void Water_Bug()
{
    for (int i = 0; i < Cloud.size(); i++)
    {
        int x = Cloud[i].first;
        int y = Cloud[i].second;
        int Cnt = 0;
        for (int j = 2; j <= 8; j += 2)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (MAP[nx][ny] >= 1) Cnt++;
        }
        MAP[x][y] += Cnt;
    }
}
 
void Delete_Cloud()
{
    Cloud.clear();
}
 
void Make_Cloud()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (Cloud_MAP[i][j] == true) continue;
            if (MAP[i][j] < 2) continue;
            MAP[i][j] -= 2;
            Cloud.push_back(make_pair(i, j));
        }
    }
 
    memset(Cloud_MAP, false, sizeof(Cloud_MAP));
    for (int i = 0; i < Cloud.size(); i++)
    {
        int x = Cloud[i].first;
        int y = Cloud[i].second;
        Cloud_MAP[x][y] = true;
    }
}
 
void Find_Answer()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            Answer += MAP[i][j];
        }
    }
}
 
void Solution()
{
    Init_Cloud();
    for (int i = 0; i < M; i++)
    {
        Move_Cloud(i);
        Make_Rain();
        Water_Bug();
        Delete_Cloud();
        Make_Cloud();
    }
    Find_Answer();
    cout << 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;
}