2021년도 상반기 삼성기출 A형 1번문제다.
구현문제 특성상 문제가 굉장히 길고, 비문학 지문을 읽는듯한 기분이든다. 차분히 읽고 기능단위로 분리하여 구현하면 되겠다. 이 문제를 풀어가능 과정에서 얻어갈 수 있는 테크닉 위주로 기록한다. 문제를 풀고 얻어가는 것이 있어야 성장할 수 있다.
범위 좌표를 벗어나 순환하는 경우
예를 들면, x 와 y 의 좌표가 1-50 인 경우 50을 넘어가면 1로 넘어가고 1 아래로 넘어가면 50으로 돌아오는 구조다. 보통의 탐색 문제에서 범위를 넘어다니며 순환하는 문제를 풀어보지 못했기 때문에 상당히 생각하는 시간이 소모되었는데, 이런식으로 구현이 가능하다.
int Make_Range(int x) {
if (x > N) {
return 1;
}
else if (x < 1) {
return N;
}
else {
return x;
}
}
좌표의 증감이 1씩 이루어진다는 가정 하에, 매개변수에 좌표 값을 넣어주면 범위에 맞는 좌표로 환산해주는 메서드다. 다만, 이 함수는 좌표의 증감이 발생할 때 마다 사용해줘야한다.
for (int n = 0; n < dist; n++) {
nx += x_move;
nx = Make_Range(nx);
// 즉시 좌표 정비
ny += y_move;
ny = Make_Range(ny);
// 즉시 좌표 정비
}이런 식으로 사용이 가능하다.
좌표 표기 [X][Y] 에 맞게 dx[] dy[] 를 수정
첫번째 포인트는, 8가지 방향을 1~8의 정수로 표현한다는 것이다. 따라서 배열의 크기는 8이 아닌 9가 맞다. 두번째 포인트는 [x][y] 식 표기를 고수하기 위해 dx[] 와 dy[] 를 뒤바꿔 설정해야 한다는 것이다. 그리고 마지막 포인트는 화살표의 방향에 속으면 안된다는 것이다. 예로, 위를 향하는 화살표라고 해서 y 좌표에 +1 연산을 하면 안된다. 위쪽 화살표는 y 좌표가 줄어들기 때문이다.
int dx[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int dy[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };따라서 이렇게 설정이 가능하다.
첫번째 풀이 후, 배열을 Vector 와 함께 사용하는 방식으로 코드를 리팩토링했다.
전체 코드는 다음과 같다.
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int N, M;
int map[51][51];
int cloud[51][51];
vector<pair<int, int>> v;
int dx[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int dy[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int Water_Copy_Dx[4] = { -1, -1, 1, 1 };
int Water_Copy_Dy[4] = { 1, -1, 1, -1 };
struct moveTo {
int direct;
int dist;
};
// 방향, 거리정보
queue<moveTo> q;
// 모든 이동이 끝나고, 바구니에 든 물의 총량
int Final_Sum() {
int sum = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
sum += map[i][j];
}
}
return sum;
}
void Input() {
// N, M 입력
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
}
}
// 방향, 거리정보
int direct, dist;
for (int i = 1; i <= M; i++) {
cin >> direct >> dist;
q.push({ direct, dist });
}
}
void Init_Cloud() {
cloud[N][1] = 1;
cloud[N][2] = 1;
cloud[N - 1][1] = 1;
cloud[N - 1][2] = 1;
v.push_back({ N, 1 });
v.push_back({ N, 2 });
v.push_back({ N - 1, 1 });
v.push_back({ N - 1, 2 });
}
// x 는 1씩 증감한다. 따라서 이동한 순간 바로 범위에 맞는 좌표로 수정한다.
int Make_Range(int x) {
if (x > N) {
return 1;
}
else if (x < 1) {
return N;
}
else {
return x;
}
}
// 구름이 움직임 -> 비가 내림 -> 구름이 사라짐
void Move_And_Rain(int direct, int dist) {
memset(cloud, 0, sizeof(cloud));
// 기존 구름의 위치정보 초기화.
for (int k = 0; k < v.size(); k++) {
int nx = v[k].first;
int ny = v[k].second;
int x_move = dx[direct]; // x 단위 이동 값
int y_move = dy[direct]; // y 단위 이동 값
for (int n = 0; n < dist; n++) {
nx += x_move;
nx = Make_Range(nx);
// 즉시 좌표 정비
ny += y_move;
ny = Make_Range(ny);
// 즉시 좌표 정비
}
v[k].first = nx;
v[k].second = ny;
// 구름 한 점 이동 완료
}
for (int k = 0; k < v.size(); k++) {
int x = v[k].first;
int y = v[k].second;
map[x][y]++; // 구름이 이동한 좌표에서 비가 내린다.
cloud[x][y] = 1; // 구름이 새롭게 이동한 좌표를 표기함.
}
}
// 물이 증가한 칸(구름이 새롭게 이동한 좌표) 에 물복사 마법을 시전
void Copy_Water() {
for (int i = 0; i < v.size(); i++) {
int x = v[i].first;
int y = v[i].second;
for (int k = 0; k < 4; k++) {
int nx = x + Water_Copy_Dx[k];
int ny = y + Water_Copy_Dy[k];
if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
if (map[nx][ny] >= 1) map[x][y]++;
}
}
v.clear();
// 구름 저장소 초기화.
}
// 물의 양이 2 이상인 칸에 구름이 생성됨, 물의 양이 2 줄어듬, moveAndRain 에서 구름이 사라진 칸이 아니여야 함.
void Create_Cloud() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (map[i][j] >= 2 && cloud[i][j] == 0) {
cloud[i][j] = 1;
v.push_back({ i, j });
map[i][j] -= 2;
}
}
}
}
int main() {
Input();
Init_Cloud();
while (!q.empty()) {
int direct = q.front().direct;
int dist = q.front().dist;
q.pop();
Move_And_Rain(direct, dist);
Copy_Water();
Create_Cloud();
}
cout << Final_Sum() << endl;
}
거창하지 않아도, 늘 꾸준히 기록하는 습관