취미생활
[C++] 마법사 상어와 비바라기 백준 문제 풀이 본문
마법사 상어와 비바라기 성공
| 1 초 (추가 시간 없음) | 1024 MB | 11382 | 5883 | 4009 | 50.019% |
문제
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.
격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.
비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.
- 모든 구름이 di 방향으로 si칸 이동한다.
- 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
- 구름이 모두 사라진다.
- 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
- 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
- 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
- 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
입력
첫째 줄에 N, M이 주어진다.
둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.
다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.
출력
첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.
제한
- 2 ≤ N ≤ 50
- 1 ≤ M ≤ 100
- 0 ≤ A[r][c] ≤ 100
- 1 ≤ di ≤ 8
- 1 ≤ si ≤ 50
예제 입력 1 복사
5 4
0 0 1 0 2
2 3 2 1 0
4 3 2 9 0
1 0 2 9 0
8 8 2 1 0
1 3
3 4
8 1
4 8
예제 출력 1 복사
77
구름이 있는 칸은 빨간색으로 표시했고, 물이 증가한 칸은 초록색으로 표시했다.
| 0 | 0 | 1 | 0 | 2 |
| 2 | 3 | 2 | 1 | 0 |
| 4 | 3 | 2 | 9 | 0 |
| 1 | 0 | 2 | 9 | 0 |
| 8 | 8 | 2 | 1 | 0 |
첫 번째 이동은 구름이 1번 방향(←)으로 3칸 이동해야 한다. 구름이 이동한 후는 다음과 같다.
| 0 | 0 | 1 | 0 | 2 |
| 2 | 3 | 2 | 1 | 0 |
| 4 | 3 | 2 | 9 | 0 |
| 1 | 0 | 2 | 9 | 0 |
| 8 | 8 | 2 | 1 | 0 |
구름이 있는 칸에 비가 1씩 내리고, 구름은 사라진다.
| 0 | 0 | 1 | 0 | 2 |
| 2 | 3 | 2 | 1 | 0 |
| 4 | 3 | 2 | 9 | 0 |
| 1 | 0 | 3 | 10 | 0 |
| 8 | 8 | 3 | 2 | 0 |
(4, 3)은 대각선 4개의 방향 모두에 물이 있다. 따라서, 물의 양이 4 증가해 7이 된다. (4, 4)는 대각선 2개의 방향(↖, ↙)에 물이 있다. 물의 양은 2 증가하고, 12가 된다. (5, 3)은 대각선으로 거리가 1인 칸이 2개(↖, ↗)있고, 이 중에서 1개(↗)만 물이 있다. 따라서, 물의 양은 3에서 4로 변한다. (5, 4)도 방향 1개(↖)만 물이 있기 때문에, 물의 양이 3이 된다.
| 0 | 0 | 1 | 0 | 2 |
| 2 | 3 | 2 | 1 | 0 |
| 4 | 3 | 2 | 9 | 0 |
| 1 | 0 | 7 | 12 | 0 |
| 8 | 8 | 4 | 3 | 0 |
이제 구름이 있었던 칸을 제외한 나머지 칸 중에서 물의 양이 2 이상인 칸에 구름이 생긴다. 구름이 생기면 물의 양이 2만큼 줄어든다.
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 7 | 0 |
| 1 | 0 | 7 | 12 | 0 |
| 6 | 6 | 4 | 3 | 0 |
두 번째 이동이 끝난 후의 상태는 다음과 같다.
| 2 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 2 |
| 5 | 4 | 5 | 5 | 0 |
| 4 | 5 | 12 | 15 | 0 |
| 4 | 4 | 2 | 1 | 0 |
다음은 세 번째 이동이 끝난 후의 상태이다.
| 4 | 2 | 4 | 0 | 2 |
| 0 | 1 | 0 | 1 | 0 |
| 3 | 2 | 3 | 3 | 0 |
| 2 | 3 | 17 | 13 | 0 |
| 2 | 2 | 0 | 1 | 0 |
모든 이동이 끝난 최종 상태는 다음과 같다.
| 2 | 4 | 2 | 2 | 4 |
| 3 | 1 | 0 | 5 | 3 |
| 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 22 | 11 | 0 |
| 4 | 5 | 0 | 3 | 2 |
예제 입력 2 복사
5 8
0 0 1 0 2
2 3 2 1 0
0 0 2 0 0
1 0 2 0 0
0 0 2 1 0
1 9
2 8
3 7
4 6
5 5
6 4
7 3
8 2
예제 출력 2 복사
41
| 2 | 1 | 1 | 0 | 0 |
| 1 | 0 | 3 | 7 | 1 |
| 1 | 1 | 9 | 0 | 0 |
| 0 | 1 | 4 | 0 | 2 |
| 2 | 1 | 2 | 1 | 1 |
예제 입력 3 복사
5 8
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 1
예제 출력 3 복사
2657
| 100 | 104 | 104 | 104 | 100 |
| 104 | 112 | 112 | 119 | 99 |
| 109 | 112 | 105 | 112 | 104 |
| 99 | 112 | 119 | 112 | 104 |
| 100 | 104 | 104 | 99 | 104 |
구현 + 시뮬레이션 문제인데
구현 난이도도 생각보다 높고 시뮬레이션도 신경쓸게 굉장히 많아 까다로운 문제였다.
푸는데는 3일 2시간씩 해서 총 6시간 정도 걸린듯 ;;;;
이거 삼성 코테 나오면 어떻게 풀지...
문제풀이
일단 내용을 쪼개보자
1. 구름이 생성된다. (초기는 (N,1), (N,2), (N-1,1), (N-2,1)
2. 구름이 d 방향으로 s만큼 이동한다.
3. 구름이 있는 칸 값 +1
4. 구름이 사라짐
5. 구름이 있던 칸에 물복사 버그
-> 5-1. 물이 있는 대각선 항아리 개수 만큼 값 추가
6. 새로운 구름 생성
-> 4에서 구름이 사라진 곳은 제외
-> 물이 2이상 있는 칸에서 구름 생성
-> 구름이 생성된 칸은 물이 2만큼 감소
7. 2번으로 이동
구현할 게 참 많다.
일단 코드부터 올리자면
#include <iostream>
#include <vector>
#include <utility>
#include <unistd.h>
#include <map>
#include <algorithm>
#include <stdlib.h>
#include <iomanip>
using namespace std;
constexpr int move(int x, int d, int n)
{
x += d;
if(x > n)
{
if(x % n == 0)
{
x = n;
}
else
{
x = x % n;
}
}
else if(x < 1)
{
x = n + x % n;
}
return x;
}
void moveTo(int arr[][101], int n, int *now_x, int *now_y, int d, int s)
{
/*
1 < now_x <= n
1 < now_y <= n
*/
static map<int, pair<int, int>> dir =
{
{1, {0, -1}},
{2, {-1, -1}},
{3, {-1, 0}},
{4, {-1, 1}},
{5, {0, 1}},
{6, {1, 1}},
{7, {1, 0}},
{8, {1, -1}}
};
int dir_x = dir[d].first * s;
int dir_y = dir[d].second * s;
*now_x = move(*now_x, dir_x, n);
*now_y = move(*now_y, dir_y, n);
}
void rainy(int arr[][101], const int &n, const vector<pair<int, int>> &cloud)
{
for(auto it : cloud)
{
const int x = it.first;
const int y = it.second;
++arr[x][y];
}
}
void copy_water(int arr[][101], const int &n, const vector<pair<int, int>> &cloud)
{
static vector<pair<int, int>> dir =
{
{-1, -1},
{-1, 1},
{1, -1},
{1, 1}
};
for(auto it : cloud)
{
const int x = it.first;
const int y = it.second;
int exist_cnt = 0;
for(auto it2 : dir)
{
int search_x = x + it2.first;
int search_y = y + it2.second;
if(arr[search_x][search_y] > 0)
{
++exist_cnt;
}
}
arr[x][y] += exist_cnt;
}
}
void make_cloud(int arr[][101], const int &n, const vector<pair<int, int>> prev_cloud, vector<pair<int, int>> *cloud)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
auto it = find_if(prev_cloud.begin(), prev_cloud.end(), [i, j](pair<int, int> arg){
if(arg.first == i && arg.second == j)
{
return true;
}
return false;
});
if(it != prev_cloud.end())
{
continue;
}
if(arr[i][j] >= 2)
{
cloud->push_back({i, j});
arr[i][j] -= 2;
}
}
}
}
int get_result(const int arr[][101], const int &n)
{
int result = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
result += arr[i][j];
}
}
return result;
}
int main(int argc, char **argv)
{
/*
1. 모든 구름이 d 방향으로 s만큼 이동한다.
2. 구름이 있는 칸에서 값 +1
3. 구름이 사라짐
4. 비가 내린 칸에 물복사 버그 실행
4-1. 대각선 방향으로 물이 있는 항아리 수 만큼 물 증가
5. 구름 생성
5-1. 3 에서 구름이 사라진 칸은 제외
5-2. 물이 2 이상 있는 칸에서 구름 생성
5-2. 구름이 생성된 칸은 물이 2만큼 감소
6. 1 번으로 이동
*/
using namespace std;
int result = 0;
int n, m;
int arr[101][101] = {0,};
cin >> n >> m;
vector<pair<int, int>> move;
for(int i = 1; i <= n; ++i) // read map
{
for(int j = 1; j <= n; ++j)
{
cin >> arr[i][j];
}
}
while(m--) // read dir and speed
{
int a, b;
cin >> a >> b;
move.push_back({a, b});
}
vector<pair<int, int>> cloud = {
{n, 1}, {n, 2}, {n-1, 1}, {n-1, 2}
};
vector<pair<int, int>> prev_cloud;
int count = 1;
for(auto it : move)
{
for(int i = 0; i < cloud.size(); ++i)
{
moveTo(arr, n, &cloud[i].first, &cloud[i].second, it.first, it.second);
}
rainy(arr, n, cloud);
copy_water(arr, n, cloud);
prev_cloud = cloud;
cloud.clear();
make_cloud(arr, n, prev_cloud, &cloud);
++count;
}
result = get_result(arr, n);
cout << result;
return 0;
}코드 전문은 이렇다.
나 같은 경우 코드가 길어지면 뭘 했는지 까먹어서 최대한 함수로 적었다.
함수 설명을 하자면
constexpr int move(int x, int d, int n)
void moveTo(int arr[][101], int n, int *now_x, int *now_y, int d, int s)
void rainy(int arr[][101], const int &n, const vector<pair<int, int>> &cloud)
void copy_water(int arr[][101], const int &n, const vector<pair<int, int>> &cloud)
void make_cloud(int arr[][101], const int &n, const vector<pair<int, int>> prev_cloud, vector<pair<int, int>> *cloud)
int get_result(const int arr[][101], const int &n)| move | 구름 이동 시, 맵을 넘어가는 것을 계산하기 위한 함수 |
| moveTo | 구름이 이동할 때 실제로 호출되는 함수 |
| rainy | 비내리기, 현재 생성된 구름을 인자로 받아 항아리 물 추가함 |
| copy_water | 물복사버그 함수, 구름 값을 인자로 받아 대각선 계산 후 값 추가 |
| make_cloud | 이전 구름 값을 참조하여 새로운 구름을 만듦 |
| get_result | 전체 항아리 물 계산용 (사실 함수로 안만들어도 됐을 듯) |
constexpr int move(int x, int d, int n)
{
x += d;
if(x > n)
{
if(x % n == 0)
{
x = n;
}
else
{
x = x % n;
}
}
else if(x < 1)
{
x = n + x % n;
}
return x;
}move 함수부터 설명을 하자면,
moveTo 에서 일부 알고리즘을 떼어서 만든 함수다.
정해질 배열 밖으로 넘어갈 경우 좌표의 반대편 끝으로 옮겨가는 공식인데
이거 생각해내는데 2시간정도 걸린 것 같다.
대학교 다닐 시절에는 이런 걸 많이해서 빨리 빨리 계산이 됐는데
실제로 현업을 뛰다보니 이제는 이런 코드를 짜는 게 익숙치가 않다.
(현업에서 이런거 쓰면 혼난다)
이걸 떼어놓은 이유는 5번 물복사버그에서 항아리 좌표 계산을 위해서 떼어놓았는데
문제를 다시보니 물복사 버그 파트에서는 항아리 좌표가 이어지지 않았다.
이거 때문에 40분은 버린 것 같은데 다음 번에는 제한사항부터 쭉 정리를 해놓고 구현을 시작해야 할 듯
void moveTo(int arr[][101], int n, int *now_x, int *now_y, int d, int s)
{
/*
1 < now_x <= n
1 < now_y <= n
*/
static map<int, pair<int, int>> dir =
{
{1, {0, -1}},
{2, {-1, -1}},
{3, {-1, 0}},
{4, {-1, 1}},
{5, {0, 1}},
{6, {1, 1}},
{7, {1, 0}},
{8, {1, -1}}
};
int dir_x = dir[d].first * s;
int dir_y = dir[d].second * s;
*now_x = move(*now_x, dir_x, n);
*now_y = move(*now_y, dir_y, n);
}그 다음으로 볼 함수는 moveTo 함수다.
구름이 이동할 때 호출할 실제 함수인데
다 만들고 보니 함수 인자로 arr를 받을 필요는 없었던 것 같다.
이 함수에서 핵심은 방향(d) 과 속도(s) 에 따른 좌표 계산 이었는데,
이런 경우 테이블을 하나 만들어서 배열 참조하는 식으로 만들면 문제를 쉽게 풀수 있다.
나는 이 문제 전까지는 이중 배열을 통해 문제를 해결했었는데
해당 문제는 c++ 스럽게 짜고 싶다는 생각이 들어 최대한 STL를 사용해봤다.
static 으로 선언해서 메모리 할당을 1회로 제한하고 사용하면 속도가 더 빠르지 않을까?
라는 생각에 static도 넣었다.
void rainy(int arr[][101], const int &n, const vector<pair<int, int>> &cloud)
{
for(auto it : cloud)
{
const int x = it.first;
const int y = it.second;
++arr[x][y];
}
}그 다음으로는 비내리기 함수인데
이건 생각보다 쉽다.
cloud 값에 들어있는 좌표로 루프를 돌리면서 값을 올려주면 된다.
void copy_water(int arr[][101], const int &n, const vector<pair<int, int>> &cloud)
{
static vector<pair<int, int>> dir =
{
{-1, -1},
{-1, 1},
{1, -1},
{1, 1}
};
for(auto it : cloud)
{
const int x = it.first;
const int y = it.second;
int exist_cnt = 0;
for(auto it2 : dir)
{
int search_x = x + it2.first; // 잘못 생각했던 지점
int search_y = y + it2.second; // 잘못 생각했던 지점
if(arr[search_x][search_y] > 0)
{
++exist_cnt;
}
}
arr[x][y] += exist_cnt;
}
}그 다음으로 물복사 버그다.
비내리기와 마찬가지로 cloud 값으로 루프를 돌렸다.
search_x, search_y를 계산하며 문제가 생겼었는데
처음에는 moveTo와 같이 배열 밖으로 넘어가면 처음 값으로 돌아가야 하는 줄 알았다.
그래서 moveTo 에서 계산 알고리즘을 떼어 내 별도 함수로 만들었는데
문제를 다시보니까 그게 아니더라..
다시 한번 느끼는 거지만,
문제를 잘 읽는 게 무엇보다도 제일 어려운 것 같다.
문제 풀 때 기능 별 제약 사항을 꼭 정리하고 문제를 풀자
void make_cloud(int arr[][101], const int &n, const vector<pair<int, int>> &prev_cloud, vector<pair<int, int>> *cloud)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
auto it = find_if(prev_cloud.begin(), prev_cloud.end(), [i, j](pair<int, int> arg){
if(arg.first == i && arg.second == j)
{
return true;
}
return false;
});
if(it != prev_cloud.end())
{
continue;
}
if(arr[i][j] >= 2)
{
cloud->push_back({i, j});
arr[i][j] -= 2;
}
}
}
}그 다음으로는 구름을 만드는 알고리즘이다.
이건 배열 전체로 루프를 돌려야했다.
전체 배열로 루프를 돌려서 이전 구름 값이 없는 경우에만 알고리즘이 계속되도록 만들었다.
값 찾는 것 때문에 lambda 와 find_if 를 사용해야 했는데,
람다 함수는 어려운 내용은 없고 그냥 첫 번째 값, 두 번째 값이 일치하는 지만 확인하는 내용이다.
람다 함수가 아무래도 보기 좀 힘든데 좀 더 깔끔하게 짜는 법을 배울 필요가 있을 듯
조건
1. 이전에 구름이 없던 지역
2. 물이 2이상인 지역
해당 조건이 일치하는 경우 물을 2만큼 감소시키고 구름 배열에 좌표를 추가한다.
int get_result(const int arr[][101], const int &n)
{
int result = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
result += arr[i][j];
}
}
return result;
}마지막 get_result는 항아리에 담긴 전체 물 양을 계산한다.
어려운 내용 없으니 패스
int main(int argc, char **argv)
{
/*
1. 모든 구름이 d 방향으로 s만큼 이동한다.
2. 구름이 있는 칸에서 값 +1
3. 구름이 사라짐
4. 비가 내린 칸에 물복사 버그 실행
4-1. 대각선 방향으로 물이 있는 항아리 수 만큼 물 증가
5. 구름 생성
5-1. 3 에서 구름이 사라진 칸은 제외
5-2. 물이 2 이상 있는 칸에서 구름 생성
5-2. 구름이 생성된 칸은 물이 2만큼 감소
6. 1 번으로 이동
*/
using namespace std;
int result = 0;
int n, m;
int arr[101][101] = {0,};
// 데이터 입력
cin >> n >> m;
vector<pair<int, int>> move;
for(int i = 1; i <= n; ++i) // read map
{
for(int j = 1; j <= n; ++j)
{
cin >> arr[i][j];
}
}
while(m--) // read dir and speed
{
int a, b;
cin >> a >> b;
move.push_back({a, b});
}
// 구름 초기값
vector<pair<int, int>> cloud = {
{n, 1}, {n, 2}, {n-1, 1}, {n-1, 2}
};
vector<pair<int, int>> prev_cloud;
int count = 1;
//실제 알고리즘 동작
for(auto it : move)
{
for(int i = 0; i < cloud.size(); ++i) // for_each 사용 금지
{
moveTo(arr, n, &cloud[i].first, &cloud[i].second, it.first, it.second);
}
rainy(arr, n, cloud);
copy_water(arr, n, cloud);
prev_cloud = cloud;
cloud.clear();
make_cloud(arr, n, prev_cloud, &cloud);
++count;
}
result = get_result(arr, n);
cout << result;
return 0;
}main 함수에서는 딱히 설명할 부분이 없는데
시행 착오 하나만 짚고 넘어가려고 한다.
moveTo 가 실행되는 부분이 for문을 통해 호출하고 있는데,
원래는 for_each 문을 사용했다가 문제가 생겼다.
moveTo 에서 변경한 내용이 적용되질 않았는데
구글링 해보니 for_each는 임시 변수로 루프를 돌리는 거라서 값을 바꿀 수가 없다고 한다.
이거 때문에 30분 정도 버린 듯 하다.
다음 번에 이런 식으로 데이터를 바꿀 일이 있다면
for_each 문 말고 일반 for문으로 루프를 돌려야 할 듯
개인적인 소감
어려운 문제는 맞지만 정리만 잘 하면 풀 수 있는 문제
다만, 푸는 시간이 정해진 상태였다면 머리털 다 뽑아버렸을 듯
'컴퓨터 > 코딩테스트' 카테고리의 다른 글
| [C++] 백준 14500 테트로미노 (0) | 2023.11.07 |
|---|---|
| [C++] 경쟁적 전염 백준 18405 문제 풀이 (1) | 2022.12.21 |
| [C++] 특정 거리의 도시 찾기 백준 18352 번 문제 풀이 (0) | 2022.12.14 |
