문제링크:www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
20년도 하반기 삼성 코딩테스트 기출문제입니다.
저는 오전에 풀어서 접하지 못했던 문제입니다.
우선 크게 구현해야하는 부분이 4가지 였습니다.
1. 입력 받기
2. 회전시키기
3. 모래 이동
4. 결과 도출
2, 3번이 핵심입니다.
우선 회전은 for문과 y_ar, x_ar(방향배열)을 통해서 구현했습니다.
가운데 점부터 시작하여 방향별로 cnt 갯수만큼 점을 옮겨줌으로서 2번 회전을 구현했습니다.
그렇다면 3번 모래 이동은 어떤식으로 구현할까요?
저는 구조체를 하나 생성했습니다.
typedef struct a {
vector <int> vec;
double per;
}moved;해당 구조체에 vec에는 모래가 이동하는 좌표로 가기위해 필요 값들을 그리고 per에는 해당 좌표에 대한 퍼센트를 기입해놓았습니다. 현재 방향에 따라서 값을 더해주는 형태로 구현했기 때문에 아래처럼 간단하게 구현할 수 있었습니다.
아래는 정답코드입니다. 해당 문제에서 주의할 점은 수의 범위가 넘어갈 때에는 예외처리를 통해서 데이터를 지우게끔 해야하는 것입니다.
#include <iostream>
#include <vector>
using namespace std;
typedef struct a {
vector <int> vec;
double per;
}moved;
int n = 0, result =0;
int arr[501][501] = { 0, };
moved val[9];
int y_ar[4] = { 0,1,0,-1 };
int x_ar[4] = { -1,0,1,0 };
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//init
val[0].vec.push_back(1), val[0].per = 0.01;
val[1].vec.push_back(3), val[1].per = 0.01;
val[2].vec.push_back(1), val[2].vec.push_back(0), val[2].per = 0.07;
val[3].vec.push_back(3), val[3].vec.push_back(0), val[3].per = 0.07;
val[4].vec.push_back(1), val[4].vec.push_back(1), val[4].vec.push_back(0), val[4].per = 0.02;
val[5].vec.push_back(3), val[5].vec.push_back(3), val[5].vec.push_back(0), val[5].per = 0.02;
val[6].vec.push_back(1), val[6].vec.push_back(0), val[6].vec.push_back(0), val[6].per = 0.1;
val[7].vec.push_back(3), val[7].vec.push_back(0), val[7].vec.push_back(0), val[7].per = 0.1;
val[8].vec.push_back(0), val[8].vec.push_back(0), val[8].vec.push_back(0), val[8].per = 0.05;
//0.
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> arr[i][j];
result += arr[i][j];
}
//1. rotate
int cy = n / 2 + 1, cx = n / 2 + 1, dir = 0, cnt = 0;
for (int k = 0; k < n * 2 - 1; k++) {
if (k % 2 == 0)
cnt++;
for (int i = 0; i < cnt; i++) { // 해당방향으로 이동
int curval = arr[cy + y_ar[dir]][cx + x_ar[dir]];
for (int j = 0; j < 9; j++) {
int ny = cy;
int nx = cx;
for (int u = 0; u < val[j].vec.size(); u++) {
ny += y_ar[(dir + val[j].vec[u]) % 4];
nx += x_ar[(dir + val[j].vec[u]) % 4];
}
if (ny >= 1 && ny <= n && nx >= 1 && nx <= n) {
arr[ny][nx] += (int)(curval * val[j].per);
}
arr[cy + y_ar[dir]][cx + x_ar[dir]] -= (int)(curval * val[j].per);
}
//알파 계산
if (cy + y_ar[dir] * 2 >= 1 && cy + y_ar[dir] * 2 <= n && cx + x_ar[dir] * 2 >= 1 && cx + x_ar[dir] * 2 <= n)
arr[cy + y_ar[dir] * 2][cx + x_ar[dir] * 2] += arr[cy + y_ar[dir]][cx + x_ar[dir]];
if(cy + y_ar[dir] >= 1 && cy + y_ar[dir] <= n && cx + x_ar[dir] >= 1 && cx + x_ar[dir] <= n)
arr[cy + y_ar[dir]][cx + x_ar[dir]] = 0;
cy += y_ar[dir], cx += x_ar[dir]; // 실제 좌표 이동
/*
cout << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cout << arr[i][j] << ' ';
cout << endl;
}*/
}
dir++;
if (dir == 4)
dir = 0;
}
int sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
sum += arr[i][j];
result -= sum;
cout << result << endl;
return 0;
}
