[BeakJoon 20057] 마법사 상어와 토네이도

안녕하세요. 이번 포스팅에서는 저번 포스팅에 이어 토네이도 문제를 풀어보도록 하겠습니다.

 

해당 문제는

https://www.acmicpc.net/problem/20057

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

 

위 링크를 통해 확인하실 수 있습니다.

 

 

이 문제는 크게 두 가지를 구현하셔야 합니다.

 

1. 토네이도 방향으로 순회

2. 방향에 맞게 흩뿌리기

 

우선 토네이도 방향으로 순회 먼저 설명드리겠습니다.

 

저 같은 경우

 

이런 식으로 진행되는 것을 알았습니다. 따라서 재귀적으로 현재 몇 번 움직였는지, 움직인 카운트가 방향을 바꿔야 하는 카운트에 도달했는지를 각각 재귀 함수로 넘겨서 구현했는데요. 

 

다른 분들 풀이 보니까 while loop를 사용해서 해결하신 분도 많더라구요. 

 

void go(int y, int x, int d, int shouldMove, int moveCnt, int dirChangeCnt) {
	if(y == 1 && x == 1) {
		return;
	}	
	
	
	if(shouldMove == moveCnt) {
		moveCnt = 0;
		d = (d+1)%4;
		dirChangeCnt++;
		if(dirChangeCnt == 2) {
			shouldMove++;
			dirChangeCnt = 0;
		}	
	}
	
	int ny = y+dir[d][0], nx = x+dir[d][1];
	
	fluid(y, x, ny, nx, d);
	go(ny, nx, d, shouldMove, moveCnt+1, dirChangeCnt);
}

 

보시면 shouldMove 변수가 1, 2, 3 이런식으로 해당 방향으로 움직여야 하는 개수입니다.

moveCnt는 현재 방향으로 몇 번 움직였나를 확인해주는 변수입니다.

 

따라서 shouldMove == moveCnt가 성립하면, 방향을 바꾸어주었습니다.

 

dirChangeCnt는 현재 shouldMove로 몇번 방향을 바꾸었나를 세어주었습니다.

 

1, 1, 2, 2, 3, 3... 이런 식으로 진행된다면, 2번 방향이 바뀔 때마다 shoulMove 변수를 1 증가시켜주었습니다.

 

 

흩뿌리기의 경우

해당 방향으로 뿌려야 하는 모든 좌표를 구한 다음, 비율에 맞게 뿌려주었습니다.

(모든 좌표를 구하는 과정이 살짝 노가다...)

 

void fluid(int fromY, int fromX, int toY, int toX, int d) {
	Node alpha, onePer1, onePer2, twoPer1, twoPer2, fivePer, sevenPer1, sevenPer2, tenPer1, tenPer2;
	vector<Node> v;
	
	int one, two, five, seven, ten, a, total = board[toY][toX];
	one = total*(0.01), two = total*(0.02), five = total*(0.05), seven = total*(0.07), ten = total*(0.1);
	a = total - (one*2 + two*2 + five + seven*2 + ten*2);
	
	alpha.m = a; alpha.y = toY + dir[d][0]; alpha.x = toX + dir[d][1];
	fivePer.m = five; fivePer.y = alpha.y + dir[d][0]; fivePer.x = alpha.x + dir[d][1];
	
	v.push_back(alpha); v.push_back(fivePer);	
	
	if(d == 0 || d == 2) {
		tenPer1.m = ten; tenPer1.y = alpha.y-1; tenPer1.x = alpha.x;
		tenPer2.m = ten; tenPer2.y = alpha.y+1; tenPer2.x = alpha.x;
		sevenPer1.m = seven; sevenPer1.y = toY-1; sevenPer1.x = toX;
		sevenPer2.m = seven; sevenPer2.y = toY+1; sevenPer2.x = toX;
		twoPer1.m = two; twoPer1.y = toY-2; twoPer1.x = toX;
		twoPer2.m = two; twoPer2.y = toY+2; twoPer2.x = toX;
		onePer1.m = one; onePer1.y = fromY-1; onePer1.x = fromX;
		onePer2.m = one; onePer2.y = fromY+1; onePer2.x = fromX;
	} else if(d == 1 || d == 3) {
		tenPer1.m = ten; tenPer1.y = alpha.y; tenPer1.x = alpha.x+1;
		tenPer2.m = ten; tenPer2.y = alpha.y; tenPer2.x = alpha.x-1;
		sevenPer1.m = seven; sevenPer1.y = toY; sevenPer1.x = toX+1;
		sevenPer2.m = seven; sevenPer2.y = toY; sevenPer2.x = toX-1;
		twoPer1.m = two; twoPer1.y = toY; twoPer1.x = toX+2;
		twoPer2.m = two; twoPer2.y = toY; twoPer2.x = toX-2;
		onePer1.m = one; onePer1.y = fromY; onePer1.x = fromX+1;
		onePer2.m = one; onePer2.y = fromY; onePer2.x = fromX-1;
	} 
	
	v.push_back(tenPer1); v.push_back(tenPer2);
	v.push_back(sevenPer1); v.push_back(sevenPer2);
	v.push_back(twoPer1); v.push_back(twoPer2);
	v.push_back(onePer1); v.push_back(onePer2);
	
	for (Node here : v) {
		if(inRange(here.y, here.x)) {
			board[here.y][here.x] += here.m;
		} else {
			res += here.m;
		}
	}
	
}

 

이런 식으로 모든 좌표를 구하고, 해당 좌표가 범위 안에 있다면, 그 좌표에 더해주고

범위 안에 없다면 결괏값에 더해주었습니다.

 

 

<소스 코드>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int n, res, board[504][504];
const int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
typedef struct __node{
	int m, y, x;
}Node;
bool inRange(int y, int x) {
	return ((y >= 1) && (x >= 1) && (y <= n) && (x <= n));
}
void fluid(int fromY, int fromX, int toY, int toX, int d) {
	Node alpha, onePer1, onePer2, twoPer1, twoPer2, fivePer, sevenPer1, sevenPer2, tenPer1, tenPer2;
	vector<Node> v;
	
	int one, two, five, seven, ten, a, total = board[toY][toX];
	one = total*(0.01), two = total*(0.02), five = total*(0.05), seven = total*(0.07), ten = total*(0.1);
	a = total - (one*2 + two*2 + five + seven*2 + ten*2);
	
	alpha.m = a; alpha.y = toY + dir[d][0]; alpha.x = toX + dir[d][1];
	fivePer.m = five; fivePer.y = alpha.y + dir[d][0]; fivePer.x = alpha.x + dir[d][1];
	
	v.push_back(alpha); v.push_back(fivePer);	
	
	if(d == 0 || d == 2) {
		tenPer1.m = ten; tenPer1.y = alpha.y-1; tenPer1.x = alpha.x;
		tenPer2.m = ten; tenPer2.y = alpha.y+1; tenPer2.x = alpha.x;
		sevenPer1.m = seven; sevenPer1.y = toY-1; sevenPer1.x = toX;
		sevenPer2.m = seven; sevenPer2.y = toY+1; sevenPer2.x = toX;
		twoPer1.m = two; twoPer1.y = toY-2; twoPer1.x = toX;
		twoPer2.m = two; twoPer2.y = toY+2; twoPer2.x = toX;
		onePer1.m = one; onePer1.y = fromY-1; onePer1.x = fromX;
		onePer2.m = one; onePer2.y = fromY+1; onePer2.x = fromX;
	} else if(d == 1 || d == 3) {
		tenPer1.m = ten; tenPer1.y = alpha.y; tenPer1.x = alpha.x+1;
		tenPer2.m = ten; tenPer2.y = alpha.y; tenPer2.x = alpha.x-1;
		sevenPer1.m = seven; sevenPer1.y = toY; sevenPer1.x = toX+1;
		sevenPer2.m = seven; sevenPer2.y = toY; sevenPer2.x = toX-1;
		twoPer1.m = two; twoPer1.y = toY; twoPer1.x = toX+2;
		twoPer2.m = two; twoPer2.y = toY; twoPer2.x = toX-2;
		onePer1.m = one; onePer1.y = fromY; onePer1.x = fromX+1;
		onePer2.m = one; onePer2.y = fromY; onePer2.x = fromX-1;
	} 
	
	v.push_back(tenPer1); v.push_back(tenPer2);
	v.push_back(sevenPer1); v.push_back(sevenPer2);
	v.push_back(twoPer1); v.push_back(twoPer2);
	v.push_back(onePer1); v.push_back(onePer2);
	
	for (Node here : v) {
		if(inRange(here.y, here.x)) {
			board[here.y][here.x] += here.m;
		} else {
			res += here.m;
		}
	}
	
}
void go(int y, int x, int d, int shouldMove, int moveCnt, int dirChangeCnt) {
	if(y == 1 && x == 1) {
		return;
	}	
	
	
	if(shouldMove == moveCnt) {
		moveCnt = 0;
		d = (d+1)%4;
		dirChangeCnt++;
		if(dirChangeCnt == 2) {
			shouldMove++;
			dirChangeCnt = 0;
		}	
	}
	
	int ny = y+dir[d][0], nx = x+dir[d][1];
	
	fluid(y, x, ny, nx, d);
	go(ny, nx, d, shouldMove, moveCnt+1, dirChangeCnt);
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> board[i][j];
		}
	}
	
	int start = n/2 + 1;
	go(start, start, 0, 1, 0, 0);
	cout << res;
	
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.