알고리즘/Baekjoon

[C++] 백준 23288번 주사위 굴리기 2

kimyunseok 2021. 10. 25. 19:02
 

23288번: 주사위 굴리기 2

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼

www.acmicpc.net

삼성 SW 역량 테스트 기출 문제 수록 문제. 

구현 / 시뮬레이션 문제이다.

이해하기 어려웠고, 시간을 잡아먹었던(자꾸 8번째 테스트 케이스가 이상하게 나와서 고쳤다.) 것들이 있었다.

조건들을 정리해가면서 문제 풀이를 정리해 보겠다.

 

문제풀이

문제의 조건들을 정리해보면, 다음과 같은 순서로 구현하면 된다.

  1. 높이, 너비, 주사위 이동횟수를 입력받는다.
  2. 격자의 각 칸의 숫자를 입력받는다.

여기까지가 기본 입력이다. 그 후에 이동횟수만큼 아래를 반복한다.

  1. 현재 주사위의 이동방향으로 주사위를 이동한다(굴린다).
    만일 이동하려는 방향에 칸이 없다면 반대 방향으로 굴린다.

  2. 이동한 칸(R, C)에서 점수를 획득한다.
    점수는 동서남북 방향으로 (R, C)와 같은 칸의 개수를 찾으면 된다. - BFS로 찾으면 된다.

  3. 마지막으로 주사위 아랫면의 숫자에 따라 다음과 같이 방향을 옮긴다.
  • 주사위 아랫면의 수 > (R, C) : 주사위 이동방향을 시계 방향으로 90도 회전한다.
  • 주사위 아랫면의 수 < (R, C) : 주사위 이동방향을 반시계 방향으로 90도 회전한다.
  • 주사위 아랫면의 수 == (R, C) : 주사위 이동방향을 변경하지 않는다.

 

위 조건들을 구현해주면 된다.

 

조건은 여기서 끝인데, 주사위 전개도를 나는 처음에 안쪽으로 접어서 주사위를 만들려 했다.

그러나 이렇게 할 경우에 주사위의 겉면이 아닌 안쪽 면에 숫자가 들어가게 되므로 틀린 조립 방식이 된다.

따라서 주사위 전개도를 바깥쪽으로 접어야 이 문제의 조건에 맞게 풀 수 있다.

 

코드를 살펴보자.

사용한 STL과 변수

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int height, width, moveCnt;
int map[21][21];
bool visit[21][21];
int curDiceBottomNum = 6;
int curDirection = 1;
int curR = 1;
int curC = 1;
int reverseDiceNum[7] = { -1, 6, 5, 4, 3, 2, 1 };
int reverseDirection[4] = {2, 3, 0, 1};
int adj[4] = { 2, 3, 5, 4 }; // 순서 : 북(0), 동(1), 남(2), 서(3)
pair<int, int> directions[4] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1}
};
int ans;
  • height, width, moveCnt : 입력받는 N, M, K
  • map 배열 : 격자의 칸 정보
  • visit 배열 : BFS를 할 때 각 좌표를 방문했는지 여부를 저장하는 배열
  • curDiceBottomNum : 현재 주사위의 어떤 수가 바닥면을 향하고 있는지 저장하는 변수
  • curDirection : 현재 방향. 0(북), 1(동), 2(남), 3(서)
  • curR, curC : 현재 주사위의 좌표
  • reverseDiceNum 배열 : 각 숫자(index)의 맞은편에 있는 수를 저장하는 배열
  • reverseDirection 배열 : 각 방향의 반대 방향을 저장하는 배열
  • adj 배열 : 현재 바닥면의 북, 동, 남, 서 방향에 존재하는 숫자를 저장해두는 배열.
  • direction 배열 : 격자에서 북, 동, 남, 서 방향으로 가기위해 더해줘야하는 값을 저장하는 배열
  • ans : 출력하는 값.

 

메인함수와 주사위 진행 메서드 go()

void go(int idx) {
	if (idx > moveCnt) { return; }

	move();
	getScore();
	setDirection();
	go(idx + 1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> height >> width >> moveCnt;

	for (int i = 1; i <= height; i++) {
		for (int j = 1; j <= width; j++) {
			cin >> map[i][j];
		}
	}

	go(1);

	cout << ans;

	return 0;
}

메인함수에서는 N, M, K와 격자의 정보를 입력받는다.

 

그리고나서 go()메서드를 출력한다. 매개변수는 현재 몇번 째 주사위를 굴릴 차례인지를 나타낸다.

go() 메서드를 보면 위에서 말한 로직이 메서드 순서대로 구현되어 있다.

그 전에 만일 주사위를 굴리는 번째 수가 주사위를 굴릴 횟수 K보다 크다면 return한다.

아니라면 다음과 같은 순서로 진행된다.

  • move() 메서드 : 주사위를 이동 방향대로 움직인다.
    void move() {
	int nxtR = curR + directions[curDirection].first;
	int nxtC = curC + directions[curDirection].second;
	if (nxtR < 1 || nxtR > height || nxtC < 1 || nxtC > width) {
		curDirection = reverseDirection[curDirection];
		nxtR = curR + directions[curDirection].first;
		nxtC = curC + directions[curDirection].second;
	}
	curR = nxtR;
	curC = nxtC;

	int prevDiceBottom = curDiceBottomNum;
	curDiceBottomNum = adj[curDirection];
	int reverse = reverseDirection[curDirection];
	adj[reverse] = prevDiceBottom;
	adj[curDirection] = reverseDiceNum[prevDiceBottom];
}​
    현재 방향에 따라 direction 배열에서 현재 좌표(R, C)값에 향하는 방향의 좌표를 구한다.
    만일 좌표가 올바르지 않다면, 반대 방향의 좌표로 현재 좌표를 이동시켜준다.

    이동시켜준 후에는 주사위의 바닥면을 바꿔준다. adj[이동방향]이 바닥면이 된다.
    이 때 주사위를 굴렸을 때는 이동한 방향과 이동한 방향의 역방향 면의
    숫자만 바뀐다는 것을 알면 이 문제를 쉽게 풀 수 있다.
    (ex. 남쪽 방향으로 굴렸다면 어차피 동, 북쪽 면의 숫자는 변하지 않는다.)
    위 로직을 그대로 구현했다.
    온 방향의 반대 방향은 이전 면이 될 것이고
    온 방향을 한번 더 가면 이전 면의 마주보는 면이 될 것이다.
    이런 식으로 인접한 네 면의 숫자를 저장하는 adj 배열의 정보를 갱신해준다.

  • getScore() 메서드 : 현재 칸에서 동서남북 방향 중 계속해서 나아갈 때, 같은 칸이 몇 개 있는지 세는 메서드 
    void getScore() {
	int cnt = 1;
	int num = map[curR][curC];
	queue<pair<int, int>> q;
	vector<pair<int, int>> visitPointVec;
	q.push({ curR, curC });
	visitPointVec.push_back({ curR, curC });
	visit[curR][curC] = true;
	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (pair<int, int> dir : directions) {
			int nxtR = r + dir.first;
			int nxtC = c + dir.second;
			if(nxtR < 1 || nxtR > height || nxtC < 1 || nxtC > width || 
				visit[nxtR][nxtC] || map[nxtR][nxtC] != num) {
				continue;
			}

			visit[nxtR][nxtC] = true;
			q.push({ nxtR, nxtC });
			visitPointVec.push_back({ nxtR, nxtC });
			cnt++;
		}
	}
	for (int i = 0; i < visitPointVec.size(); i++) {
		int r = visitPointVec[i].first;
		int c = visitPointVec[i].second;
		visit[r][c] = false;
	}
	ans = ans + (cnt * num);
}​
     BFS를 통해서 현재 칸과 같은 숫자의 칸들만 탐사해서 몇 개의 칸이 있는지 센다.
    이 때, 좌표를 visitPointVec이라는 벡터에 넣어주어서 visit 배열을 다시 false로 처리할 때의 시간을 줄였다.
    후에 ans에 '현재 칸의 수 * 같은 숫자의 칸의 개수'를 더해준다.

  • setDirection() 메서드 : 주사위 아랫면에 따라 이동방향을 설정해주는 메서드.
    void setDirection() {
	int mapNum = map[curR][curC];
	if (curDiceBottomNum > mapNum) {
		curDirection = curDirection + 1;
	}
	else if (curDiceBottomNum < mapNum) {
		curDirection = curDirection - 1;
	}

	//오래걸린이유, 주사위의 방향 조건을 < 0일 땐 3으로 주고 > 3일 땐 0으로 줘야하는데, 두 조건 모두 0으로 줘버림.
	if (curDirection < 0 ) {
		curDirection = 3;
	}
	else if(curDirection > 3){
		curDirection = 0;
	}
}​
    위에서 설명했듯이, 여기가 내가 실수했던 부분이다.
    주석에도 나와있듯이 주사위의 방향 숫자가 음수일 땐 3으로, 4 이상일 땐 0으로 바꿔줘야 하는데
    두 조건 모두 0으로 만들었다.
    테케 7번까지 잘 나왔는데 8번부터 엄청 큰 수가 나오길래 뭘 잘못했지 생각했는데 이 부분이였다.

    아무튼 주사위 아랫면의 수와 현재 칸의 수를 비교한 후에 이동방향을 설정해준다.

  • go(idx + 1) : 다음 번째 굴릴 차례로 넘어간다.

 

이제 go()메서드가 끝이났으면 ans값을 출력하면 된다.

 

 

1. 주사위 전개도 잘못 조립

2. 방향 overflow 잘못 설정

 

 

GitHub - kimyunseok/cpp: my study-record

my study-record. Contribute to kimyunseok/cpp development by creating an account on GitHub.

github.com

코드 전문은 위에서 확인이 가능하다.