BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST A형)

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

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

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

input은 아래처럼 처리한다.
BOJ 14499 : 주사위 굴리기는 (0, 0) 부터 시작하였으나 여기서는 (1, 1)부터 시작한다.

#define MAX (20 + 5)

int N, M, K;
int MAP[MAX][MAX];

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);
}

BOJ 14499 : 주사위 굴리기를 참고하여 주사위를 아래와 같이 정의한다.

typedef struct st1
{
	int up;
	int left; int top; int right;
	int down;
	int buttom;
}DICE;

DICE dice;

주사위의 네 방향 이동은 아래와 같은 함수로 처리한다.

void(*MOVE[6])(void);

void moveEast()
{
	int tmp[6] = { dice.up, dice.left, dice.top, dice.right, dice.down, dice.buttom };

	dice.top = tmp[1];
	dice.right = tmp[2];
	dice.buttom = tmp[3];
	dice.left = tmp[5];
}

void moveWest()
{
	int tmp[6] = { dice.up, dice.left, dice.top, dice.right, dice.down, dice.buttom };

	dice.top = tmp[3];
	dice.right = tmp[5];
	dice.buttom = tmp[1];
	dice.left = tmp[2];
}

void moveNorth()
{
	int tmp[6] = { dice.up, dice.left, dice.top, dice.right, dice.down, dice.buttom };

	dice.up = tmp[2];
	dice.top = tmp[4];
	dice.down = tmp[5];
	dice.buttom = tmp[0];
}

void moveSouth()
{
	int tmp[6] = { dice.up, dice.left, dice.top, dice.right, dice.down, dice.buttom };

	dice.up = tmp[5];
	dice.top = tmp[0];
	dice.down = tmp[2];
	dice.buttom = tmp[4];
}

동서남북에 대해 define으로 번호를 매겨주고, dr, dc 배열로 방향을 정의한다.

#define EAST (1)
#define WEST (2)
#define NORTH (3)
#define SOUTH (4)

...

/* 순서대로 0, 동, 서, 북, 남 */
int dr[] = { 0, 0, 0, -1, 1 };
int dc[] = { 0, 1, -1, 0, 0 };

함수와 define이 정의되었으면, main에서 MOVE에 대한 함수를 mapping 하면 된다.

int main(void)
{
	
    ...
    
	MOVE[EAST] = moveEast;
	MOVE[WEST] = moveWest;
	MOVE[NORTH] = moveNorth;
	MOVE[SOUTH] = moveSouth;

	...
}

이 문제에서는 방향 변경에 대한 처리가 세 가지가 필요하다.

MAP을 벗어나는 경우 반대 방향 전환, 시계, 반시계 방향 전환이 있다.

main에서 배열을 정의하여 각 방향에 대한 처리를 해둔다.

int main(void)
{
	...
    
	int changeDir[5] = { 0 };
	int changeClock[5] = { 0 };
	int changeCounterClock[5] = { 0 };
	
	changeDir[EAST] = WEST;
	changeDir[WEST] = EAST;
	changeDir[NORTH] = SOUTH;
	changeDir[SOUTH] = NORTH;

	changeClock[EAST] = SOUTH;
	changeClock[SOUTH] = WEST;
	changeClock[WEST] = NORTH;
	changeClock[NORTH] = EAST;

	changeCounterClock[EAST] = NORTH;
	changeCounterClock[NORTH] = WEST;
	changeCounterClock[WEST] = SOUTH;
	changeCounterClock[SOUTH] = EAST;
    
    ...
}

그리고 scoreBoard라는 배열에 미리 점수를 기록해둔다.

주사위가 놓인 칸과 같은 값의 주사위만 돌아다닐 수 있으므로, 점수는 항상 고정된다.

BOJ 2667 : 단지번호붙이기에서 BFS를 이용한 방법으로 score를 구할 수 있다.

wp가 (r, c)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 C가 되고,

MAP[r][c]가 이동할 수 있는 칸의 같은 값인 정수 B가 된다.

/* 순서대로 0, 동, 서, 북, 남 */
int dr[] = { 0, 0, 0, -1, 1 };
int dc[] = { 0, 1, -1, 0, 0 };

int scoreBoard[MAX][MAX];
int BFS(int r, int c)
{
	int wp, rp, number;
	int visit[MAX][MAX] = { 0 };

	wp = rp = 0;

	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = 1;
	number = MAP[r][c];
	
	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 1; i <= 4; i++) // 4방향을 dr, dc의 1 ~ 4로 정의
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr <= 0 || nc <= 0 || nr > N || nc > M) continue;

			if (visit[nr][nc] == 0 && number == MAP[nr][nc])
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;
			}
		}
	}

	return wp * number; // (r, c)에 대한 점수 B * C 의 값
}

위의 함수를 이용해 scoreBoard에 값을 채운다.

주사위에 최초의 값을 넣어주고, (row, col) = (1, 1), dir = EAST로 초기화 해준 후에 K번 주사위를 이동하면 된다.

이동 방향에 칸이 없는 경우에 대해 dir 처리를 해준 후, 주사위를 움직인다.

점수 계산을 하고 주사위의 아랫면과 MAP[r][c]를 비교한 후에 다시 방향처리를 한다.

방향 처리가 완료되면 row, col을 갱신한다.

int main(void)
{
	...

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scoreBoard[r][c] = BFS(r, c); // 미리 점수를 구한다.

	dice.up = 2;
	dice.left = 4; dice.top = 1; dice.right = 3;
	dice.down = 5;
	dice.buttom = 6;

	row = 1, col = 1, dir = EAST;
	score = 0;

	for (int i = 0; i < K; i++)
	{
		int nr, nc, A, B;

		nr = row + dr[dir];
		nc = col + dc[dir];

		if (nr <= 0 || nc <= 0 || nr > N || nc > M)
		{
			dir = changeDir[dir];
			nr = row + dr[dir];
			nc = col + dc[dir];
		}

		MOVE[dir]();

		score += scoreBoard[nr][nc];

		A = dice.buttom;
		B = MAP[nr][nc];
		
		if (A > B) dir = changeClock[dir];
		else if (A < B) dir = changeCounterClock[dir];
		// else { 변화 없음. }
		
		row = nr;
		col = nc;
	}

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

	return 0;
}

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (20 + 5)

#define EAST (1)
#define WEST (2)
#define NORTH (3)
#define SOUTH (4)

int N, M, K;
int MAP[MAX][MAX];

typedef struct st1
{
	int up;
	int left; int top; int right;
	int down;
	int buttom;
}DICE;

DICE dice;

typedef struct st2
{
	int r;
	int c;
}RC;

RC queue[MAX * MAX];

void(*MOVE[6])(void);

void moveEast()
{
	int tmp[6] = { dice.up, dice.left, dice.top, dice.right, dice.down, dice.buttom };

	dice.top = tmp[1];
	dice.right = tmp[2];
	dice.buttom = tmp[3];
	dice.left = tmp[5];
}

void moveWest()
{
	int tmp[6] = { dice.up, dice.left, dice.top, dice.right, dice.down, dice.buttom };

	dice.top = tmp[3];
	dice.right = tmp[5];
	dice.buttom = tmp[1];
	dice.left = tmp[2];
}

void moveNorth()
{
	int tmp[6] = { dice.up, dice.left, dice.top, dice.right, dice.down, dice.buttom };

	dice.up = tmp[2];
	dice.top = tmp[4];
	dice.down = tmp[5];
	dice.buttom = tmp[0];
}

void moveSouth()
{
	int tmp[6] = { dice.up, dice.left, dice.top, dice.right, dice.down, dice.buttom };

	dice.up = tmp[5];
	dice.top = tmp[0];
	dice.down = tmp[2];
	dice.buttom = tmp[4];
}

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);
}

void output()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
}

void outputDice()
{
	printf("  %d\n", dice.up);
	printf("%d %d %d\n", dice.left, dice.top, dice.right);
	printf("  %d\n", dice.down);
	printf("  %d\n", dice.buttom);
	putchar('\n');
}

/* 순서대로 0, 동, 서, 북, 남 */
int dr[] = { 0, 0, 0, -1, 1 };
int dc[] = { 0, 1, -1, 0, 0 };

int scoreBoard[MAX][MAX];
int BFS(int r, int c)
{
	int wp, rp, number;
	int visit[MAX][MAX] = { 0 };

	wp = rp = 0;

	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = 1;
	number = MAP[r][c];
	
	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 1; i <= 4; i++) // 4방향을 dr, dc의 1 ~ 4로 정의
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr <= 0 || nc <= 0 || nr > N || nc > M) continue;

			if (visit[nr][nc] == 0 && number == MAP[nr][nc])
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;
			}
		}
	}

	return wp * number; // (r, c)에 대한 점수 B * C 의 값
}

int main(void)
{
	int row, col, dir;
	int changeDir[5] = { 0 };
	int changeClock[5] = { 0 };
	int changeCounterClock[5] = { 0 };
	int score;

	input();

	MOVE[EAST] = moveEast;
	MOVE[WEST] = moveWest;
	MOVE[NORTH] = moveNorth;
	MOVE[SOUTH] = moveSouth;

	changeDir[EAST] = WEST;
	changeDir[WEST] = EAST;
	changeDir[NORTH] = SOUTH;
	changeDir[SOUTH] = NORTH;

	changeClock[EAST] = SOUTH;
	changeClock[SOUTH] = WEST;
	changeClock[WEST] = NORTH;
	changeClock[NORTH] = EAST;

	changeCounterClock[EAST] = NORTH;
	changeCounterClock[NORTH] = WEST;
	changeCounterClock[WEST] = SOUTH;
	changeCounterClock[SOUTH] = EAST;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scoreBoard[r][c] = BFS(r, c); // 미리 점수를 구한다.

	dice.up = 2;
	dice.left = 4; dice.top = 1; dice.right = 3;
	dice.down = 5;
	dice.buttom = 6;

	row = 1, col = 1, dir = EAST;
	score = 0;

	for (int i = 0; i < K; i++)
	{
		int nr, nc, A, B;

		nr = row + dr[dir];
		nc = col + dc[dir];

		if (nr <= 0 || nc <= 0 || nr > N || nc > M)
		{
			dir = changeDir[dir];
			nr = row + dr[dir];
			nc = col + dc[dir];
		}

		MOVE[dir]();

		score += scoreBoard[nr][nc];

		A = dice.buttom;
		B = MAP[nr][nc];
		
		if (A > B) dir = changeClock[dir];
		else if (A < B) dir = changeCounterClock[dir];
		// else { 변화 없음. }
		
		row = nr;
		col = nc;
	}

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

	return 0;
}

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

BOJ 23290 : 마법사 상어와 복제 (삼성 SW TEST A형) (0)	2021.11.06
BOJ 23289 : 온풍기 안녕! (삼성 SW TEST A형) (0)	2021.11.06
BOJ 21611 : 마법사 상어와 블리자드 (삼성 SW TEST A형) (0)	2021.05.01
BOJ 21610 : 마법사 상어와 비바라기 (삼성 SW TEST A형) (0)	2021.04.30
BOJ 21609 : 상어 중학교 (삼성 SW TEST A형) (0)	2021.04.29

피로물든딸기의 라이브러리

BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST A형)

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

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

댓글

티스토리툴바

BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST A형)

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

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

관련글

댓글

티스토리툴바