백준 14499번 주사위 굴리기 (삼성 SW 역량테스트 기출문제)

사용한 알고리즘: 구현...?


상당히 까다로운 구현 문제였습니다.
바꿔말하면 구현만 정말 열심히하면 되는 문제였습니다.

우선 방향 동,서,남,북을 각각 0,1,2,3 의 번호를 붙여서 생각했습니다.
이후 주사위를 '동-서 방향으로 움직일 때를 고려한 row 라는 행렬' 과,
'남-북 방향으로 움직일 때를 고려한 col 라는 행렬' 로 생각했습니다.
각 주사위를 row[4], col[4]로 나누어 생각한 후,
이때 주사위 윗면을 row[1] = col[1] , 주사위 밑면을 row[3] = col[3]으로 생각했습니다.
(row 와 col 은 2면이 겹친다. -> 주사위는 6면체)
즉, row[4] = row[0](옆면1) ,  row[1](윗면),  row[2](옆면2),  row[3](밑면) 으로 구성되고
col 도 마찬가지입니다.

이때 주의할 점이,
(1) 동-서 로 움직인 후 (row 행렬을 조작 후 )
     col[1] = row[1] (윗면이 같음을 생각),  col[3] = row[3] (아랫면이 같음을 생각)
(2) 남-북 으로 움직인 후 (col 행렬을 조작 후)
     row[1] = col[1] (윗면이 같음을 생각), row[3] = col[3] (아랫면이 같음을 생각)
위 두가지를 생각해 주어야 한다는 것입니다.

예를들어 동쪽으로 주사위가 움직이는걸 생각해보면,
row[2] = row[1] ;  윗면이 옆면1로 내려감        ( row[1] (윗면) -> row[2] (옆면2) )
row[1] = row[0] ;  옆면1이 윗면으로 올라옴     ( row[0] (옆면1) -> row[1] (윗면) )
row[0] = row[3] ;  밑면이 옆면1로 올라감         ( row[3] (밑면) -> row[0] (옆면1) )
row[3] = row[2] ;   옆면2가 밑면으로 내려감      ( row[2] (옆면2) -> row[3] (밑면) )

위 과정과 같이 움직이는 것을 알 수 있습니다.

이때 도착하는 칸에 숫자가 0 이어서 밑면이 옆면의 숫자로 바뀔지,
아니면 도착하는 칸에 숫자가 0이 아니어서 해당 칸 숫자로 바뀔지를 추가로 생각해주면 됩니다.

또한 위에 써놓은 주의할 점 을 잘 생각하여 동쪽으로 움직임에도 col 의 윗면과 밑면은 바뀐다는 것을 생각하여
col[1] (윗면) = row[1] , col[3] (밑면) = row[3] 을 취해주면 됩니다.


정말 단순하지만 헷갈리기 쉽고 구현이 까다로운 문제였습니다....
화이팅이요..!

	#include <bits/stdc++.h>
	using namespace std;
	int N, M, x, y, K, dir, arr[21][21];
	// 동, 서, 북, 남;
	int dx[4] = {0,0,-1,1};
	int dy[4] = {1,-1,0,0};
	// row[3] = col[3] // row[1] = col[1]
	// 윗면은 row[1] or col[1]
	int row[4];
	int col[4];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M >> x >> y >> K;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < M; ++j)
	cin >> arr[i][j];
	for (int i = 0; i < K; ++i){
	cin >> dir;
	dir--;
	int nx = x+dx[dir];
	int ny = y+dy[dir];
	if(nx<0||nx>=N||ny<0||ny>=M) continue;
	x+=dx[dir];
	y+=dy[dir];
	int next = arr[nx][ny];
	int temp = 0;
	// 동쪽 이동 - row
	if(dir==0){
	if(next==0){
	temp = row[2];
	arr[nx][ny] = temp;
	}
	else{
	temp = arr[nx][ny];
	arr[nx][ny] = 0;
	}
	row[2] = row[1];
	row[1] = row[0];
	row[0] = row[3];
	row[3] = temp;
	col[1] = row[1];
	col[3] = temp;
	cout << row[1] << '\n';
	}
	// 서쪽 이동 - row
	else if(dir==1){
	if(next==0){
	temp = row[0];
	arr[nx][ny] = temp;
	}
	else{
	temp = arr[nx][ny];
	arr[nx][ny] = 0;
	}
	row[0] = row[1];
	row[1] = row[2];
	row[2] = row[3];
	row[3] = temp;
	col[1] = row[1];
	col[3] = temp;
	cout << row[1] << '\n';
	}
	// 북쪽 이동 - row
	else if(dir==2){
	if(next==0){
	temp = col[0];
	arr[nx][ny] = temp;
	}
	else{
	temp = arr[nx][ny];
	arr[nx][ny] = 0;
	}
	col[0] = col[1];
	col[1] = col[2];
	col[2] = col[3];
	col[3] = temp;
	row[1] = col[1];
	row[3] = temp;
	cout << col[1] << '\n';
	}
	// 남쪽 이동 - row
	else if(dir==3){
	if(next==0){
	temp = col[2];
	arr[nx][ny] = temp;
	}
	else{
	temp = arr[nx][ny];
	arr[nx][ny] = 0;
	}
	col[2] = col[1];
	col[1] = col[0];
	col[0] = col[3];
	col[3] = temp;
	row[1] = col[1];
	row[3] = temp;
	cout << col[1] << '\n';
	}
	}
	return 0;
	}

view raw BOJ 14499.cpp hosted with ❤ by GitHub