문제

BOJ 14499, 주사위 굴리기

핵심

• 입력의 크기가 $10^3$이라 구현에 초점을 맞춘다.
• 매번 규칙에 맞게 주사위를 이동시키며, 주사위 윗면에 있는 값을 출력하도록 한다. 주사위의 전개도는 아래와 같다. 윗면이 1이고, 동쪽을 바라보는 방향이 3이며, 주사위 바닥면은 6을 나타낸다.

  2
4 1 3
  5
  6

• 주사위를 위, 아래, 왼쪽, 오른쪽으로 굴릴 수 있다. 굴리고 나서 이동한 칸에 쓰여 있는 수가 0이면 주사위 바닥 면에 쓰여 있는 수가 복사되고, 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위 바닥 면으로 복사되어 칸에 쓰여 있는 수가 0이 된다는 규칙이 있다. 추가로 주사위를 지도의 바깥으로 이동시키려고 할 때는 무시해야 한다.
• 주사위를 방향대로 굴리는 것을 직관적으로 구현하면 된다. 주사위를 담을 2차원 배열을 선언하고, 굴리기 전의 상태를 복사하여 주사위값을 안전하게 복사하였다.

int dice[4][3];
int tmp[4][3];
/*
0 2 0      0 2 0
4 1 3  --> 6 4 1
0 5 0	   0 5 0
0 6 0	   0 3 0
*/
void rollRight() {
	dice[1][0] = tmp[3][1];
	dice[1][1] = tmp[1][0];
	dice[1][2] = tmp[1][1];
	dice[3][1] = tmp[1][2];
};

/*
0 2 0      0 2 0
4 1 3  --> 1 3 6
0 5 0      0 5 0
0 6 0      0 4 0
*/
void rollLeft() {
	dice[1][0] = tmp[1][1];
	dice[1][1] = tmp[1][2];
	dice[1][2] = tmp[3][1];
	dice[3][1] = tmp[1][0];
};

/*
0 2 0      0 1 0
4 1 3  --> 4 5 3
0 5 0      0 6 0
0 6 0      0 2 0
*/
void rollUp() {
	dice[0][1] = tmp[1][1];
	dice[1][1] = tmp[2][1];
	dice[2][1] = tmp[3][1];
	dice[3][1] = tmp[0][1];
};

/*
0 2 0      0 6 0
4 1 3  --> 4 2 3
0 5 0      0 1 0
0 6 0      0 5 0
*/
void rollDown() {
	dice[0][1] = tmp[3][1];
	dice[1][1] = tmp[0][1];
	dice[2][1] = tmp[1][1];
	dice[3][1] = tmp[2][1];
}

개선

코드

시간복잡도

• $O(k)$

C++

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

int dice[4][3];
int tmp[4][3];
int map[24][24];
int dy[] = {0, 0, 0, -1, 1};
int dx[] = {0, 1, -1, 0, 0};
int n, m, y, x, k;
void rollRight() {
	dice[1][0] = tmp[3][1];
	dice[1][1] = tmp[1][0];
	dice[1][2] = tmp[1][1];
	dice[3][1] = tmp[1][2];
};

void rollLeft() {
	dice[1][0] = tmp[1][1];
	dice[1][1] = tmp[1][2];
	dice[1][2] = tmp[3][1];
	dice[3][1] = tmp[1][0];
};

void rollUp() {
	dice[0][1] = tmp[1][1];
	dice[1][1] = tmp[2][1];
	dice[2][1] = tmp[3][1];
	dice[3][1] = tmp[0][1];
};

void rollDown() {
	dice[0][1] = tmp[3][1];
	dice[1][1] = tmp[0][1];
	dice[2][1] = tmp[1][1];
	dice[3][1] = tmp[2][1];
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> y >> x >> k;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j)
			cin >> map[i][j];
	}	
	vector<int>path;
	while (k--) {
		int dir;
		cin >> dir;
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m)
			continue;
		y = ny;
		x = ny;
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 3; ++j)
				tmp[i][j] = dice[i][j];
		}
		if (dir == 1) 
			rollRight();
		else if (dir == 2)
			rollLeft();
		else if (dir == 3)
			rollUp();
		else
			rollDown();
		if (map[y][x] == 0) 
			map[y][x] = dice[3][1];
		else {
			dice[3][1] = map[y][x];
			map[y][x] = 0;
		}
		path.push_back(dice[1][1]);
	}
	for (int i = 0; i < (int)path.size(); ++i) {
		cout << path[i] << '\n';
	}
}

Java

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n, m, y, x, k;
    static int[][] dice = new int[4][3];
    static int[][] tmp = new int[4][3];
    static int[][] map = new int[24][24];
    static int[] dy = {0, 0, 0, -1, 1};
    static int[] dx = {0, 1, -1, 0, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> path = new ArrayList<>();
        while (k-- > 0) {
            int dir = Integer.parseInt(st.nextToken());
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m)
                continue;
            y = ny;
            x = nx;
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < 3; ++j)
                    tmp[i][j] = dice[i][j];
            }
            if (dir == 1)
                rollRight();
            else if (dir == 2)
                rollLeft();
            else if (dir == 3)
                rollUp();
            else
                rollDown();
            if (map[y][x] == 0)
                map[y][x] = dice[3][1];
            else {
                dice[3][1] = map[y][x];
                map[y][x] = 0;
            }
            path.add(dice[1][1]);
        }
        for (var e : path)
            bw.write(e + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    static void rollRight() {
        dice[1][0] = tmp[3][1];
        dice[1][1] = tmp[1][0];
        dice[1][2] = tmp[1][1];
        dice[3][1] = tmp[1][2];
    };

    static void rollLeft() {
        dice[1][0] = tmp[1][1];
        dice[1][1] = tmp[1][2];
        dice[1][2] = tmp[3][1];
        dice[3][1] = tmp[1][0];
    };

    static void rollUp() {
        dice[0][1] = tmp[1][1];
        dice[1][1] = tmp[2][1];
        dice[2][1] = tmp[3][1];
        dice[3][1] = tmp[0][1];
    };

    static void rollDown() {
        dice[0][1] = tmp[3][1];
        dice[1][1] = tmp[0][1];
        dice[2][1] = tmp[1][1];
        dice[3][1] = tmp[2][1];
    }
}