(c++)백준 20057번: 마법사 상어와 토네이도

www.acmicpc.net/problem/20057

20057번: 마법사 상어와 토네이도

[풀이]

문제에 있는 조건들을 구현하면 되는 문제였다.

 

구현한 것

1. 토네이도 모양대로 이동하기

-while문 안에 for문 두 개로 구현하였다. 헷갈려서 Map 배열에 경로 저장하고 출력하여 확인했다.

-방향은 왼쪽 → 아래쪽 → 오른쪽 → 위쪽 순서 반복

 

2. 모래를 비율과 a가 적혀있는 칸으로 이동시키기(방향 생각!)

-비율을 p정수 배열에 저장해놓고, 왼쪽, 아래쪽, 오른쪽, 위쪽 방향마다 해당 비율이 y기준으로 어디있는지 저장해두었다.

-격자 밖으로 이동하는 모래는 모두 변수 Sand에 더해주었다.

#include <iostream>
using namespace std;

int N;
int A[500][500];
//int Map[500][500] = { 0, };//토네이도 경로 확인용
int Sand = 0;
const int dxy[][2] = { {0,-1},{1,0},{0,1},{-1,0} };
const int dleft[][2] = { {0,-2},{-1,-1},{-2,0},{-1,0},{-1,1},{1,1},{2,0},{1,0},{1,-1} };//토네이도가 왼쪽으로 이동할 때 모래가 휘날리는 위치
const int dright[][2] = { {0,2},{-1,1},{-2,0},{-1,0},{-1,-1},{1,-1},{2,0},{1,0},{1,1} };//토네이도가 오른쪽으로 이동할 때 모래가 휘날리는 위치
const int dup[][2] = { {-2,0},{-1,-1},{0,-2},{0,-1},{1,-1},{1,1},{0,2},{0,1},{-1,1} };//토네이도가 위쪽으로 이동할 때 모래가 휘날리는 위치
const int ddown[][2] = { {2,0},{1,1},{0,2},{0,1},{-1,1},{-1,-1},{0,-2},{0,-1},{1,-1} };//토네이도가 아래쪽으로 이동할 때 모래가 휘날리는 위치
int p[9] = { 5,10,2,7,1,1,2,7,10 };//위치에 따른 비율

void MoveSand(int x, int y, int d) {
	int s = A[x][y];//(x,y)에 있던 모래의 양
	int nx;
	int ny;
	int ns;
	//방향이 왼쪽이면
	if (d == 0) {
		for (int n = 0; n < 9; n++) {
			nx = x + dleft[n][0];
			ny = y + dleft[n][1];
			ns = (s * p[n]) / 100;//(nx,ny)로 이동할 모래의 양
			A[x][y] -= ns;
			//격자 밖으로 이동하면
			if (nx <= 0 || nx > N || ny <= 0 || ny > N) {
				Sand += ns;
			}
			else {
				A[nx][ny] += ns;
			}
		}
		//a위치에도 모래 이동
		nx = x;
		ny = y - 1;
		//격자 밖으로 이동하면
		if (nx <= 0 || nx > N || ny <= 0 || ny > N) {
			Sand += A[x][y];
		}
		else {
			A[nx][ny] += A[x][y];
		}
	}
	//방향이 아래쪽이면
	else if (d == 1) {
		for (int n = 0; n < 9; n++) {
			nx = x + ddown[n][0];
			ny = y + ddown[n][1];
			ns = (s * p[n]) / 100;//(nx,ny)로 이동할 모래의 양
			A[x][y] -= ns;
			//격자 밖으로 이동하면
			if (nx <= 0 || nx > N || ny <= 0 || ny > N) {
				Sand += ns;
			}
			else {
				A[nx][ny] += ns;
			}
		}
		//a위치에도 모래 이동
		nx = x + 1;
		ny = y;
		//격자 밖으로 이동하면
		if (nx <= 0 || nx > N || ny <= 0 || ny > N) {
			Sand += A[x][y];
		}
		else {
			A[nx][ny] += A[x][y];
		}
	}
	//방향이 오른쪽이면
	else if (d == 2) {
		for (int n = 0; n < 9; n++) {
			nx = x + dright[n][0];
			ny = y + dright[n][1];
			ns = (s * p[n]) / 100;//(nx,ny)로 이동할 모래의 양
			A[x][y] -= ns;
			//격자 밖으로 이동하면
			if (nx <= 0 || nx > N || ny <= 0 || ny > N) {
				Sand += ns;
			}
			else {
				A[nx][ny] += ns;
			}
		}
		//a위치에도 모래 이동
		nx = x;
		ny = y + 1;
		//격자 밖으로 이동하면
		if (nx <= 0 || nx > N || ny <= 0 || ny > N) {
			Sand += A[x][y];
		}
		else {
			A[nx][ny] += A[x][y];
		}
	}
	//방향이 위쪽이면
	else if (d == 3) {
		for (int n = 0; n < 9; n++) {
			nx = x + dup[n][0];
			ny = y + dup[n][1];
			ns = (s * p[n]) / 100;//(nx,ny)로 이동할 모래의 양
			A[x][y] -= ns;
			//격자 밖으로 이동하면
			if (nx <= 0 || nx > N || ny <= 0 || ny > N) {
				Sand += ns;
			}
			else {
				A[nx][ny] += ns;
			}
		}
		//a위치에도 모래 이동
		nx = x - 1;
		ny = y;
		//격자 밖으로 이동하면
		if (nx <= 0 || nx > N || ny <= 0 || ny > N) {
			Sand += A[x][y];
		}
		else {
			A[nx][ny] += A[x][y];
		}
	}
	A[x][y] = 0;
}

void Tornado(int startpos) {
	int x = startpos;
	int y = startpos;
	int turn = 0;//몇 번 방향 바꿨는지
	int len = 1;//그 방향으로 이동할 칸 수
	while (1) {
		if (x == 1 && y == 1)
			break;
		//왼,아래,오,위 순서로 이동
		for (int d = 0; d < 4; d++) {
			if (turn == 2) {
				turn = 0;
				len++;
			}
			//len칸 이동하면서 모래 이동시키기
			for (int c = 1; c <= len; c++) {
				//토네이도 이동
				x += dxy[d][0];
				y += dxy[d][1];
				//다음칸에 먼지가 있으면
				if (A[x][y] != 0)
					MoveSand(x, y, d);
				//Map[x][y] = 1;//토네이도 경로 확인용
				/*
				for (int i = 1; i <= N; i++) {
					for (int j = 1; j <= N; j++)
						cout << A[i][j] << ' ';
					cout << '\n';
				}
				cout << '\n';*/
				if (x == 1 && y == 1)
					break;
			}
			if (x == 1 && y == 1)
				break;
			turn++;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j];
		}
	}
	//가운데 칸
	int m = (N / 2) + 1;
	Tornado(m);
	cout << Sand << '\n';
	return 0;
}