백준 23288 - 주사위 굴리기2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/23288

23288번: 주사위 굴리기 2

삼성 SW 역량테스트 기출문제입니다.

주사위 굴리기 + BFS가 합쳐진 문제였습니다.

문제 조건

출력 예시

주사위를 동서남북으로 바꿀때, 값이 어떻게 변하는지를 나타냈습니다.

이를 통해서 주사위를 구리는 것을 구현할 수 있습니다.

 

1. 주사위 방향 바꾸기

int change_way_180(int x) {
	if (x == 0 || x == 2) return x + 1;
	else return x - 1;
}

int change_way_90(int x, int y) {
	if (y == 1) {
		if (x == 0) return 2;
		else if (x == 1) return 3;
		else if (x == 2) return 1;
		else return 0;
	}
	else {
		if (x == 0) return 3;
		else if (x == 1) return 2;
		else if (x == 2) return 0;
		else return 1;
	}
}

1. 반대 방향으로 움직일 경우 : 동 <-> 서,  남 <-> 북 임으로 값을 바꿔주면 됩니다.

2. 시계 방향으로 움직일 경우 : 동 -> 남 , 서 -> 북 , 남 -> 서 , 북 -> 동  임으로 값을 바꿔주면 됩니다.

3. 반시계 방향으로 움직일 경우 : 동 -> 북  , 서 -> 남 , 남 -> 동 , 북 -> 서 임으로 값을 바꿔주면 됩니다.

 

 

2. 주사위 이동하기

int move_dice(int x) {
	int next_dice[7];
	int point = 0;
	int xx = dice_location.first + dx[way];
	int yy = dice_location.second + dy[way];
	if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
		for (int i = 0; i < 7; i++) {
			next_dice[i] = dice[dice_move[way][i]];
		}
		for (int i = 0; i < 7; i++) {
			dice[i] = next_dice[i];
		}
		if (dice[6] > map[xx][yy]) {
			way = change_way_90(way, 1);
		}
		else if (dice[6] < map[xx][yy]) {
			way = change_way_90(way, -1);
		}
		point = map[xx][yy] * check[xx][yy];
		dice_location = { xx,yy };
	}
	else{
		way = change_way_180(way);
		xx = dice_location.first + dx[way];
		yy = dice_location.second + dy[way];
		for (int i = 0; i < 7; i++) {
			next_dice[i] = dice[dice_move[way][i]];
		}
		for (int i = 0; i < 7; i++) {
			dice[i] = next_dice[i];
		}
		if (dice[6] > map[xx][yy]) {
			way = change_way_90(way, 1);
		}
		else if (dice[6] < map[xx][yy]) {
			way = change_way_90(way, -1);
		}
		point = map[xx][yy] * check[xx][yy];
		dice_location = { xx,yy };
	}
	return point;
}

주사위가 이동할 수 있는 경우는 2가지입니다.

1. 이동한 곳이 좌표를 벗어나지 않을때 -> 해당 좌표로 이동한다.

2. 이동한 곳이 좌표를 벗어날때 -> 이동 방향을 180도 바꾼뒤, 다시 이동한다.

다음 좌표로 이동했다면, 다음 이동 방향을 정해야합니다. A와 B의 값을 통해 방향을 정하니 이를 구현합니다.

 

한번 이동할 때마다 얻을 수 있는 점수는 map[xx][yy]의 값 * 해당 좌표에서 이동할 수 있는 좌표의 수 임으로 이를 더해줍니다.

 

 

3. (X,Y)에서 이동할 수 있는 값 구하기

void get_point(int x, int y, int cnt) {
	queue<pair<int, int>> q, location;
	int many = 1;
	q.push(make_pair(x, y));
	location.push(make_pair(x, y));
	check[x][y] = 1;
	while (!q.empty()) {
		int x1 = q.front().first;
		int y1 = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x1 + dx[i];
			int yy = y1 + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
				if (check[xx][yy] == 0 && map[xx][yy] == cnt) {
					location.push(make_pair(xx, yy));
					q.push(make_pair(xx, yy));
					check[xx][yy] = 1;
					many++;
				}
			}
		}
	}
	while (!location.empty()) {
		check[location.front().first][location.front().second] = many;
		location.pop();
	}
}

(X , Y) 좌표에서 이동할 수 있는 좌표의 수를 구하는 코드입니다.

BFS 탐색을 통해서 몇개의 좌표를 이동할 수 있는지를 찾은뒤, 이동한 좌표에 해당 값을 전부 넣었습니다.

 

 

문제 접근 방법

1. (X , Y)에서 이동할 수 있는 좌표의 값을 먼저 구해줍니다.

2. 동쪽으로 이동하는 것을 시작으로 주사위를 K번 이동해줍니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int N, M, K;
int dice_move[4][7] = { // 0번째 배열은 안쓰는 칸
	{ 0,4,2,1,6,5,3 },  // 동
	{ 0,3,2,6,1,5,4 },  // 서
	{ 0,2,6,3,4,1,5 },  // 남
	{ 0,5,1,3,4,6,2 }   // 북
	
};
int map[21][21];
int check[21][21];
pair<int, int> dice_location = { 1,1 };
int dice[7] = { 0,1,2,3,4,5,6 };  //주사위 아랫면의 값은 6번(0번에서 시작)
int dx[4] = { 0,0,1,-1 }; //동서남북
int dy[4] = { 1,-1,0,0 };
int way = 0; // 시작할 때 이동방향 = 동쪽

int change_way_180(int x) {
	if (x == 0 || x == 2) return x + 1;
	else return x - 1;
}

int change_way_90(int x, int y) {
	if (y == 1) {
		if (x == 0) return 2;
		else if (x == 1) return 3;
		else if (x == 2) return 1;
		else return 0;
	}
	else {
		if (x == 0) return 3;
		else if (x == 1) return 2;
		else if (x == 2) return 0;
		else return 1;
	}
}

int move_dice(int x) {
	int next_dice[7];
	int point = 0;
	int xx = dice_location.first + dx[way];
	int yy = dice_location.second + dy[way];
	if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
		for (int i = 0; i < 7; i++) {
			next_dice[i] = dice[dice_move[way][i]];
		}
		for (int i = 0; i < 7; i++) {
			dice[i] = next_dice[i];
		}
		if (dice[6] > map[xx][yy]) {
			way = change_way_90(way, 1);
		}
		else if (dice[6] < map[xx][yy]) {
			way = change_way_90(way, -1);
		}
		point = map[xx][yy] * check[xx][yy];
		dice_location = { xx,yy };
	}
	else{
		way = change_way_180(way);
		xx = dice_location.first + dx[way];
		yy = dice_location.second + dy[way];
		for (int i = 0; i < 7; i++) {
			next_dice[i] = dice[dice_move[way][i]];
		}
		for (int i = 0; i < 7; i++) {
			dice[i] = next_dice[i];
		}
		if (dice[6] > map[xx][yy]) {
			way = change_way_90(way, 1);
		}
		else if (dice[6] < map[xx][yy]) {
			way = change_way_90(way, -1);
		}
		point = map[xx][yy] * check[xx][yy];
		dice_location = { xx,yy };
	}
	return point;
}

void get_point(int x, int y, int cnt) {
	queue<pair<int, int>> q, location;
	int many = 1;
	q.push(make_pair(x, y));
	location.push(make_pair(x, y));
	check[x][y] = 1;
	while (!q.empty()) {
		int x1 = q.front().first;
		int y1 = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x1 + dx[i];
			int yy = y1 + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
				if (check[xx][yy] == 0 && map[xx][yy] == cnt) {
					location.push(make_pair(xx, yy));
					q.push(make_pair(xx, yy));
					check[xx][yy] = 1;
					many++;
				}
			}
		}
	}
	while (!location.empty()) {
		check[location.front().first][location.front().second] = many;
		location.pop();
	}
}

void solve() {
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (check[i][j] == 0) {
				get_point(i, j, map[i][j]);
			}
		}
	}
	for (int i = 0; i < K; i++) {
		ans += move_dice(way);
	}
	cout << ans;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!