BOJ 20057 : 마법사 상어와 토네이도 (삼성 SW TEST A형)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/20057

 

이후 설명 및 입/출력은 링크 참고

시뮬레이션 문제이므로, 그대로 구현하면 된다.

 

구현 전에 토네이도의 규칙을 알아보자.

먼저 토네이도는 최초로 ←로 움직인다. 그리고 순서대로 ↓, →, ↑로 움직이며 4방향을 반복한다.

따라서 0, 1, 2, 3을 왼쪽, 아래, 오른쪽, 위로 정의한다.

/* 순서대로 왼쪽, 아래, 오른쪽, 위 */
int dr[] = { 0, 1, 0, -1 };
int dc[] = { -1, 0, 1, 0 };

 

모래가 일정 비율로 흩날리게 되므로, 모래를 기준으로 좌표를 미리 정해둔다.

위에서부터 왼쪽으로 순서대로 0, 1, 2, ..., 8까지 번호를 매긴다.

a 위치의 경우는 마지막 남은 모래를 옮겨야 하므로 9(마지막 번호)로 번호를 매긴다.

 

번호를 매겼으면, y에 대한 각 상대좌표는 아래와 같다.

예를 들어 10%는 y: (r, c)를 기준으로 1: (r - 1, c - 1)과 5: (r + 1, r - 1)이 된다.

위 좌표는 왼쪽(0) ←방향에 대한 좌표이므로 4방향에 대해 2차원 배열을 만든다. 

int moveR[4][10] = 
{
	{ -2, -1, -1, -1,  0,  1,  1,  1,  2,  0 }, /* 왼쪽 */
	{  0,  1,  0, -1,  2,  1,  0, -1,  0,  1 }, /* 아래 */
	{ -2, -1, -1, -1,  0,  1,  1,  1,  2,  0 }, /* 오른쪽 */
	{  0, -1,  0,  1, -2, -1,  0,  1,  0, -1 }  /* 위 */
};

int moveC[4][10] = 
{
	{  0, -1,  0,  1, -2, -1,  0,  1,  0, -1 },
	{ -2, -1, -1, -1,  0,  1,  1,  1,  2,  0 },
	{  0,  1,  0, -1,  2,  1,  0, -1,  0,  1 },
	{ -2, -1, -1, -1,  0,  1,  1,  1,  2,  0 }
};

 

표에 해당하는 비율은 ratio 배열에 저장해둔다.

int ratio[9] = { 2, 10, 7, 1, 5, 10, 7, 1, 2 };

---

이제 시뮬레이션 해보자. (N = 7인 경우)

방향은 ←, ↓, →, ↑로 바뀌지만, 움직이는 횟수는 1, 1, 2, 2, 3, 3, ... , 6, 6, 7로 2회마다 1번씩 증가하고

마지막 N = 7에 대해서는 7회가 1번만 실행된다.

(즉, N = 7일 때, (1 ~ 6) x 2회 / 7 x 1회)

따라서 처음에 for문 1번에 dir을 2번 증가, count는 1번 증가하도록 구성하고, 마지막 1회는 for문 밖에서 실행한다.

매번 토네이도가 움직일 때마다, moveSand 함수를 이용해, 바깥으로 빠져나가는 모래를 counting한다.

int simulate()
{
	int outSand, dir, sr, sc, count;

	sr = sc = N / 2;
	outSand = dir = 0; /* 방향은 왼쪽부터 시작 */

	count = 1;
	for (int i = 0; i < N; i++)
	{
		for (int k = 0; k < count; k++)
		{
			sr += dr[dir % 4];
			sc += dc[dir % 4];

			outSand += moveSand(sr, sc, dir);
		}

		dir++;

		for (int k = 0; k < count; k++)
		{
			sr += dr[dir % 4];
			sc += dc[dir % 4];

			outSand += moveSand(sr, sc, dir);
		}

		dir++;
		count++;
	}

	sr += dr[dir % 4];
	sc += dc[dir % 4];

	outSand += moveSand(sr, sc, dir);

	return outSand;
}

 

moveSand 함수는 정의한 좌표와 ratio 배열 등을 이용해 옮겨주기만 하면된다.

i가 9인 경우는 남은 모래를 a로 움직이는 경우이다.

좌표의 범위가 벗어나면 ret에 모래를 누적하고, 그렇지 않은 경우는 지도에 그대로 누적한다.

int moveSand(int r, int c, int dir)
{
	int ret, pos, sand;

	ret = 0, pos = A[r][c];
	for (int i = 0; i < 10; i++) 
	{
		if (i == 9) sand = A[r][c]; /* 남아 있는 모래를 a로 이동하는 경우 */
		else
		{
			sand = pos * ratio[i] / 100;
			A[r][c] -= sand;
		}

		int nr, nc;

		nr = r + moveR[dir % 4][i];
		nc = c + moveC[dir % 4][i];
		
        /* 밖으로 나간 모래의 양 */
		if (nr < 0 || nr > N - 1 || nc < 0 || nc > N - 1) ret += sand;
		else A[nr][nc] += sand;
	}

	return ret;
}

보통 문제에서 범위를 벗어나는 경우 주변을 벽을 세우지만,

이 문제는 2칸 이상 모래가 움직이므로 MAP을 벗어나는 경계 조건을 직접 체크한다.

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (500 + 20)

int N;
int A[MAX][MAX];

void input()
{
	scanf("%d", &N);
	
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			scanf("%d", &A[r][c]);
}

/* 순서대로 왼쪽, 아래, 오른쪽, 위 */
int dr[] = { 0, 1, 0, -1 };
int dc[] = { -1, 0, 1, 0 };

int ratio[9] = { 2, 10, 7, 1, 5, 10, 7, 1, 2 };

int moveR[4][10] = 
{
	{ -2, -1, -1, -1,  0,  1,  1,  1,  2,  0 },
	{  0,  1,  0, -1,  2,  1,  0, -1,  0,  1 },
	{ -2, -1, -1, -1,  0,  1,  1,  1,  2,  0 },
	{  0, -1,  0,  1, -2, -1,  0,  1,  0, -1 }
};

int moveC[4][10] = 
{
	{  0, -1,  0,  1, -2, -1,  0,  1,  0, -1 },
	{ -2, -1, -1, -1,  0,  1,  1,  1,  2,  0 },
	{  0,  1,  0, -1,  2,  1,  0, -1,  0,  1 },
	{ -2, -1, -1, -1,  0,  1,  1,  1,  2,  0 }
};

int moveSand(int r, int c, int dir)
{
	int ret, pos, sand;

	ret = 0, pos = A[r][c];
	for (int i = 0; i < 10; i++) 
	{
		if (i == 9) sand = A[r][c]; /* 남아 있는 모래를 a로 이동 */
		else
		{
			sand = pos * ratio[i] / 100;
			A[r][c] -= sand;
		}

		int nr, nc;

		nr = r + moveR[dir % 4][i];
		nc = c + moveC[dir % 4][i];

		if (nr < 0 || nr > N - 1 || nc < 0 || nc > N - 1) ret += sand;
		else A[nr][nc] += sand;
	}

	return ret;
}

int simulate()
{
	int outSand, dir, sr, sc, count;

	sr = sc = N / 2;
	outSand = dir = 0; /* 방향은 왼쪽부터 시작 */

	count = 1;
	for (int i = 0; i < N; i++)
	{
		for (int k = 0; k < count; k++)
		{
			sr += dr[dir % 4];
			sc += dc[dir % 4];

			outSand += moveSand(sr, sc, dir);
		}

		dir++;

		for (int k = 0; k < count; k++)
		{
			sr += dr[dir % 4];
			sc += dc[dir % 4];

			outSand += moveSand(sr, sc, dir);
		}

		dir++;
		count++;
	}

	sr += dr[dir % 4];
	sc += dc[dir % 4];

	outSand += moveSand(sr, sc, dir);

	return outSand;
}

int main(void)
{
	input();

	printf("%d\n", simulate());

	return 0;
}