BOJ 백준 14499 주사위 굴리기

 

문제 : https://www.acmicpc.net/problem/14499

 

[ 문제 요약 ]

• N*M 크기의 지도가 주어지며 지도의 오른쪽은 동, 위는 북쪽입니다.
• 지도의 좌표는 (y, x)로 나타내며 y는 북쪽으로부터 떨어진 칸 개수, x는 서쪽으로 떨어진 칸 개수입니다.(문제 지문에서는 좌표가 (x, y)라고 반대로 적혀있어 헷갈립니다. 저는 (y, x)로 표기)
• 주사위의 전개도는 아래와 같습니다.

  2
4 1 3
  5
  6

 

• 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여 있고 가장 처음 주사위에는 모든 면에 0이 적혀있습니다.
• 지도의 각 칸에는 정수가 하나씩 쓰여있습니다.
• 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 지도에 복사됩니다. 0이 아닌 경우 지도에 쓰여 있는 수가 주사위 바닥으로 복사되며 지도에 쓰여 있는 수는 0이 됩니다.
• 주사위를 놓은 곳의 좌표와 이동시키는 명령이 주어질 때, 주사위가 이동했을 때마다 상단에 쓰여 있는 값을 구하는 프로그램을 작성합니다.
• 주사위는 지도 바깥으로 이동할 수 없습니다. 만약 바깥으로 이동시키려고 하는 입력인 경우 해당 명령을 무시하고, 출력도 하지 않습니다.
• 처음 주사위를 놓은 칸에 쓰여 있는 수는 항상 0입니다.

 

[ 테스트 케이스 설명 ]

4 2 0 0 8 // 세로크기(1<=20), 가로크기(1<=20), 주사위의 좌표 y(0<=N-1), x(0<=N-1), 명령어 개수(1<=1,000)
0 2 // 세로 크기만큼 반복되며 지도에 적힌 값이 주어짐(0<10)
3 4
5 6
7 8
4 4 4 1 3 3 3 2// 이동 명령어 : 동(1) 서(2) 북(3) 남(4)
이동시마다 윗 면에 쓰여 있는 수를 출력 만약 바깥으로 이동시 해당 명령 무시 및 미 출력함
0
0
3
0
0
8
6
3

 

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

이 문제는 단순 구현 문제에 가깝다 생각합니다. 주의할 것은 문제에서 좌표 설명 시 x가 세로를 의미하고 y가 가로를 의미하도록 적었습니다. 헷갈릴 수 있습니다. 그리고 주사위를 굴리는 게 그냥 옆으로 이동하는 게 아니라 한 바퀴를 굴리는 것입니다.

 

문제 해결을 간단하게 하기 위해 다음과 같은 흐름으로 코드를 작성할 수 있습니다.

 

1. 이동 명령어 입력받음
2. 명령어대로 주사위의 현재 좌표 변경
3. 명령어대로 주사위를 굴림 (주사위 평면도 내의 숫자 위치 변경)
4. 주사위의 바닥면 or 지도 숫자 변경
5. 주사위의 가장 윗면 출력

생각해야 할 것은 주사위가 동서남북으로 굴릴 때 좌표가 어떻게 변경되느냐입니다.

 

어디로 굴리든 주사위 숫자 평면도는 4개만 변경되는 규칙이 있습니다.

 

아래 코드는 주사위 평면도를 2차원 좌표에 놓고 동서남북을 갱신하는 코드와 이를 조금 더 간소화해 1차원 좌표에서 주사위 평면도를 구현하는 코드 2개를 보여줍니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	
	static final int dirInfo[][][] = {
											{{1,1},{1,2},{3,1},{1,0}},// 동
											{{1,1},{1,0},{3,1},{1,2}},// 서
											{{1,1},{0,1},{3,1},{2,1}},// 북
											{{1,1},{2,1},{3,1},{0,1}}// 남
									};
	static int dxy[][] = {{0,1},{0,-1},{-1,0},{1,0}};
	static int Y, X, ny, nx, k;
	static int[][] dice,map;

	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Y = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		ny = Integer.parseInt(st.nextToken());
		nx = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new int[Y][X];
		dice = new int[4][3];
		
		for(int y=0; y<Y; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<X; x++)
				map[y][x] = Integer.parseInt(st.nextToken());
		}
		
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		while(k-->0)
		{
			int m = Integer.parseInt(st.nextToken()) - 1;// 이동 명령어 : 동(1) 서(2) 북(3) 남(4)
			
			ny += dxy[m][0];// 다음 좌표 갱신
			nx += dxy[m][1];// 다음 좌표 갱신
			
			if(ny<0 || nx<0 || Y<=ny || X<=nx) // 좌표가 유효하지 않은 경우 좌표 원복 및 다음 연산 진행
			{
				ny -= dxy[m][0];
				nx -= dxy[m][1];
				continue;
			}
			
			move(m);// 주사위를 해당 방향으로 굴림
			changeNumber();// 바뀐 주사위의 바닥면 or 지도의 숫자 변경
			
			sb.append(dice[1][1]).append('\n');
		}
		
		System.out.print(sb);
	}
	static void move(int m) {
		int dir[][] = dirInfo[m];
		
		int last = dice[dir[3][0]][dir[3][1]];

		for(int i=3; i>0; i--)
			dice[dir[i][0]][dir[i][1]] = dice[dir[i-1][0]][dir[i-1][1]];
		
		dice[dir[0][0]][dir[0][1]] = last;
	}
	static void changeNumber() {
		if(map[ny][nx] == 0)// 이동한 칸에 쓰여 있는 수가 0이면, 주사위 바닥면에 쓰여 있는 숫자를 지도에 복사
		{
			map[ny][nx] = dice[3][1];
			return;
		}
		// 이동한 칸에 쓰여 있는 수가 0이 아니면 지도에 쓰여 있는 수가 주사위 바닥으로 복사되고 지도는 0이되면
		dice[3][1] = map[ny][nx];
		map[ny][nx] = 0;
	}
}

 

[ 정답 코드 2 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	
	static final int dirInfo[][] = {
										{0,1,5,2},// 동
										{0,2,5,1},// 서
										{0,3,5,4},// 북
										{0,4,5,3}// 남
									};
	static int dxy[][] = {{0,1},{0,-1},{-1,0},{1,0}};
	static int Y, X, ny, nx, k;
	static int[][] map;
	static int[] dice;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Y = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		ny = Integer.parseInt(st.nextToken());
		nx = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new int[Y][X];
		dice = new int[6];
		
		for(int y=0; y<Y; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<X; x++)
				map[y][x] = Integer.parseInt(st.nextToken());
		}
		
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		while(k-->0)
		{
			int m = Integer.parseInt(st.nextToken()) - 1;// 이동 명령어 : 동(1) 서(2) 북(3) 남(4)
			
			ny += dxy[m][0];// 다음 좌표 갱신
			nx += dxy[m][1];// 다음 좌표 갱신
			
			if(ny<0 || nx<0 || Y<=ny || X<=nx) // 좌표가 유효하지 않은 경우 좌표 원복 및 다음 연산 진행
			{
				ny -= dxy[m][0];
				nx -= dxy[m][1];
				continue;
			}
			
			move(m);// 주사위를 해당 방향으로 굴림
			changeNumber();// 바뀐 주사위의 바닥면 or 지도의 숫자 변경
			
			sb.append(dice[0]).append('\n');
		}
		
		System.out.print(sb);
	}
	static void move(int m) {
		int dir[] = dirInfo[m];
		
		int last = dice[dir[3]];

		for(int i=3; i>0; i--)
			dice[dir[i]] = dice[dir[i-1]];
		
		dice[dir[0]] = last;
	}
	static void changeNumber() {
		if(map[ny][nx] == 0)// 이동한 칸에 쓰여 있는 수가 0이면, 주사위 바닥면에 쓰여 있는 숫자를 지도에 복사
		{
			map[ny][nx] = dice[5];
			return;
		}
		// 이동한 칸에 쓰여 있는 수가 0이 아니면 지도에 쓰여 있는 수가 주사위 바닥으로 복사되고 지도는 0이되면
		dice[5] = map[ny][nx];
		map[ny][nx] = 0;
	}
}

 

[ 여러 반례들 ]

3 3 1 1 9
1 2 3
4 0 5
6 7 8
1 3 2 2 4 4 1 1 3
이하 답
0
0
0
3
0
1
0
6
0
///////////////////////
2 2 0 0 16
0 2
3 4
4 4 4 4 1 1 1 1 3 3 3 3 2 2 2 2
이하 답
0
0
0
0
///////////////////////

3 3 0 0 16
0 1 2
3 4 5
6 7 8
4 4 1 1 3 3 2 2 4 4 1 1 3 3 2 2
이하 답
0
0
0
6
0
8
0
2
0
8
0
2
0
8
0
2
///////////////////////////
2 10 0 5 18
6 7 7 4 3 0 5 4 3 9
8 6 9 3 2 5 1 4 5 3
4 2 4 3 4 2 4 2 3 4 2 1 2 2 2 4 2 2
이하 답
0
0
0
0
5
2
0
2
3
2
3
9
//////////////////////////////////////
3 7 0 3 11
8 3 6 0 6 9 4
8 3 0 9 5 0 2
3 4 9 3 8 8 1
1 4 2 1 4 1 3 2 2 3 2
이하 답
0
0
0
0
6
9
0
6
5
8
5
/////////////////////
4 2 3 0 8
1 0
1 3
5 1
2 0
2 4 4 3 3 1 3 2
이하 답
0
0
0
5
0
///////////////////////
5 4 1 2 20
4 4 3 5 
0 6 8 4 
0 3 1 0 
7 6 6 4 
0 3 3 7 
1 4 4 1 2 2 1 3 4 2 1 3 2 4 1 4 2 2 2 4
이하 답
0
0
4
0
4
0
0
0
4
0
0
4
0
0
3
0
3
///////////////////////////
3 5 1 2 30
6 7 3 1 4
4 8 0 5 8
1 2 9 6 2
3 4 1 2 2 2 1 4 3 4 1 3 4 3 3 2 4 2 2 4 2 4 2 1 3 1 3 3 4 1
이하
0
0
0
0
5
0
5
3
5
3
4
5
4
5
9
3
5
4
7
5
4
1
2
1
8