728x90
문제 : www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
문제설명
단순 구현 시뮬레이션 문제이다.
알고리즘
1. 문제 설명에 나와있는 5x5의 흩날리는 비율을 각 토네이도 방향마다 적용시켜준다.
2. 4방향 모두 만들어준다.
3. 토네이도를 이동하며 방향에 맞는 배열을 적용시켜 계산한다.
주의사항
1. 구현 문제는 조건을 주의해야한다. 조건을 미리 종이나 메모장에 적어논 다음 코딩하는 것이 실수를 줄이는 방법같다.
2. 4방향 마다 조건을 맞춰가며 해결했는데 미리 배열 4개를 만들어놓고 그대로 적용하는 것이 가독성이 좋은 것 같다.
구현
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int N;
int board[499][499];
int sum;
int dirr[4][2] = { {0,-1},{1,0},{0,1},{-1,0} };
void rotatemap(int dir, int y, int x) { //y,x 좌표는 토네이동 도착좌표
int remain = 0;
//무조건 좌표는 고정 2,2
if (dir == 0) //우에서좌
{
int temp = board[y][x] * 0.02;
if (y - 2 < 0)
sum += temp;
else
board[y - 2][x] += temp;
if (y + 2 > N - 1)
sum += temp;
else
board[y + 2][x] += temp;
remain += temp + temp;
temp = board[y][x] * 0.01;
if (x + 1 > N - 1)
sum += temp + temp;
else
{
if (y + 1 > N - 1)
sum += temp;
else
board[y + 1][x + 1] += temp;
if (y - 1 < 0)
sum += temp;
else
board[y - 1][x + 1] += temp;
}
remain += temp + temp;
temp = board[y][x] * 0.07;
if (y + 1 > N - 1)
sum += temp;
else
board[y + 1][x] += temp;
if (y - 1 < 0)
sum += temp;
else
board[y - 1][x] += temp;
remain += temp + temp;
temp = board[y][x] * 0.1;
if (x - 1 < 0)
sum += temp + temp;
else
{
if (y + 1 > N - 1)
sum += temp;
else
board[y + 1][x - 1] += temp;
if (y - 1 < 0)
sum += temp;
else
board[y - 1][x - 1] += temp;
}
remain += temp + temp;
temp = board[y][x] * 0.05;
if (x - 2 < 0)
sum += temp;
else
board[y][x - 2] += temp;
remain += temp;
if (x - 1 < 0)
sum += board[y][x] - remain;
else
board[y][x - 1] += board[y][x] - remain;
board[y][x] = 0;
}
else if (dir == 2) // 좌에서 우
{
int temp = board[y][x] * 0.02;
if (y - 2 < 0)
sum += temp;
else
board[y - 2][x] += temp;
if (y + 2 > N - 1)
sum += temp;
else
board[y + 2][x] += temp;
remain += temp + temp;
temp = board[y][x] * 0.1;
if (x + 1 > N - 1)
sum += temp + temp;
else
{
if (y + 1 > N - 1)
sum += temp;
else
board[y + 1][x + 1] += temp;
if (y - 1 < 0)
sum += temp;
else
board[y - 1][x + 1] += temp;
}
remain += temp + temp;
temp = board[y][x] * 0.07;
if (y + 1 > N - 1)
sum += temp;
else
board[y + 1][x] += temp;
if (y - 1 < 0)
sum += temp;
else
board[y - 1][x] += temp;
remain += temp + temp;
temp = board[y][x] * 0.01;
if (x - 1 < 0)
sum += temp + temp;
else
{
if (y + 1 > N - 1)
sum += temp;
else
board[y + 1][x - 1] += temp;
if (y - 1 < 0)
sum += temp;
else
board[y - 1][x - 1] += temp;
}
remain += temp + temp;
temp = board[y][x] * 0.05;
if (x + 2 > N - 1)
sum += temp;
else
board[y][x + 2] += temp;
remain += temp;
if (x + 1 > N - 1)
sum += board[y][x] - remain;
else
board[y][x + 1] += board[y][x] - remain;
board[y][x] = 0;
}
else if (dir == 1) // 상에서 하
{
int temp = board[y][x] * 0.02;
if (x - 2 < 0)
sum += temp;
else
board[y][x - 2] += temp;
if (x + 2 > N - 1)
sum += temp;
else
board[y][x + 2] += temp;
remain += temp + temp;
temp = board[y][x] * 0.1;
if (y + 1 > N - 1)
sum += temp + temp;
else
{
if (x + 1 > N - 1)
sum += temp;
else
board[y + 1][x + 1] += temp;
if (x - 1 < 0)
sum += temp;
else
board[y + 1][x - 1] += temp;
}
remain += temp + temp;
temp = board[y][x] * 0.07;
if (x + 1 > N - 1)
sum += temp;
else
board[y][x + 1] += temp;
if (x - 1 < 0)
sum += temp;
else
board[y][x - 1] += temp;
remain += temp + temp;
temp = board[y][x] * 0.01;
if (y - 1 < 0)
sum += temp + temp;
else
{
if (x + 1 > N - 1)
sum += temp;
else
board[y - 1][x + 1] += temp;
if (x - 1 < 0)
sum += temp;
else
board[y - 1][x - 1] += temp;
}
remain += temp + temp;
temp = board[y][x] * 0.05;
if (y + 2 > N - 1)
sum += temp;
else
board[y + 2][x] += temp;
remain += temp;
if (y + 1 > N - 1)
sum += board[y][x] - remain;
else
board[y + 1][x] += board[y][x] - remain;
board[y][x] = 0;
}
else if (dir == 3) // 하에서 상
{
int temp = board[y][x] * 0.02;
if (x - 2 < 0)
sum += temp;
else
board[y][x - 2] += temp;
if (x + 2 > N - 1)
sum += temp;
else
board[y][x + 2] += temp;
remain += temp + temp;
temp = board[y][x] * 0.01;
if (y + 1 > N - 1)
sum += temp + temp;
else
{
if (x + 1 > N - 1)
sum += temp;
else
board[y + 1][x + 1] += temp;
if (x - 1 < 0)
sum += temp;
else
board[y + 1][x - 1] += temp;
}
remain += temp + temp;
temp = board[y][x] * 0.07;
if (x + 1 > N - 1)
sum += temp;
else
board[y][x + 1] += temp;
if (x - 1 < 0)
sum += temp;
else
board[y][x - 1] += temp;
remain += temp + temp;
temp = board[y][x] * 0.1;
if (y - 1 < 0)
sum += temp + temp;
else
{
if (x + 1 > N - 1)
sum += temp;
else
board[y - 1][x + 1] += temp;
if (x - 1 < 0)
sum += temp;
else
board[y - 1][x - 1] += temp;
}
remain += temp + temp;
temp = board[y][x] * 0.05;
if (y - 2 < 0)
sum += temp;
else
board[y - 2][x] += temp;
remain += temp;
if (y - 1 < 0)
sum += board[y][x] - remain;
else
board[y - 1][x] += board[y][x] - remain;
board[y][x] = 0;
}
//printf("sum = %d renmain = %d\n", sum,remain);
}
void printboard()
{
for (size_t i = 0; i < N; i++)
{
for (size_t j = 0; j < N; j++)
{
printf("%d ", board[i][j]);
}
printf("\n");
}
printf("\n");
}
void solve()
{
int ny = N / 2;
int nx = N / 2;
int val = 1;
for (size_t k = 0; k < N / 2; k++) // 4번 회전하는 횟수
{
int cnt = 0;
for (size_t i = 0; i < 4; i++) // 4번 회전 방향
{
for (size_t j = 0; j < val; j++) // 주어진 방향에서 몇번 움직이냐
{
ny += dirr[i][0];
nx += dirr[i][1];
if (board[ny][nx] == 0)
continue;
rotatemap(i, ny, nx);
//printboard();
}
cnt++;
if (cnt % 2 == 0)
val++;
//dir 0이면 좌 우 1이면 우 좌 2면 상하 3면 하 상
}
}
for (size_t i = 0; i < N - 1; i++) // 오른쪽에서 왼쪽으로 가는 첫번째 행은 위 알고리즘에 적용 안되기에 따로 해준다.
{
ny += dirr[0][0];
nx += dirr[0][1];
if (board[ny][nx] == 0)
continue;
rotatemap(0, ny, nx);
//printboard();
}
printf("%d", sum);
}
void input()
{
scanf("%d", &N);
for (size_t i = 0; i < N; i++)
{
for (size_t j = 0; j < N; j++)
{
scanf("%d", &board[i][j]);
}
}
}
int main() {
input();
solve();
}배운점
구현 문제가 많아지는 추세이니 단순하게 생각하자!
'코딩테스트 준비하기 > 시뮬레이션 & 자료구조' 카테고리의 다른 글
| 백준 - 괄호의 값 (C++) (0) | 2021.08.17 |
|---|---|
| 백준 - 마법사 상어와 파이어스톰 (C++) (0) | 2020.11.29 |
| 5650. [모의 SW 역량테스트] 핀볼 게임 (JAVA) (0) | 2020.04.17 |
| K번째 문자열 (0) | 2020.03.17 |
| 파핑파핑 지뢰찾기 (0) | 2020.03.17 |