Categories
Tags
Algorithm Backend Backtracking Base-64 인코딩 Binary Search Bitmask Bitwise Operation Boundary Cache-Control CI-CD Content-negotiation CORS CPU Scheduling DDNS Dependency Graph Difference Array Docker File Upload Git GitHub Actions Graph Greedy Greedy Algorithm Home Server HTTP HTTP 기본 인증 HTTP 완벽 가이드 HTTP2.0 HTTPS HTTP버전 Infra Java LeetCode Linux Memory Management NAT Network Nginx On-Premise Optimization Problem OPTION 메소드 Paging Parametric Search Performance Port Forwarding Prefix Sum Primality Test proxy Range Update Review robots.txt Server Simulation Sliding Window Sorting Spring Boot SSH SSL, TLS Submodule Tailscale TCP 커넥션 Topological Sort TRACE 메소드 UA (User Agent) URL Virtualization (OS) VPN 검색 엔진 국제화 내용 협상 무중단 배포 엔터티와 인코딩 웹 로봇 웹 서버 지속 커넥션 캐시 쿠키 크롤러 클라이언트 식별 트랜스 코딩 프록시
1111 words
6 minutes
[BOJ 14499] 주사위 굴리기
문제
https://www.acmicpc.net/problem/14499
문제 이해
크게 두 가지 동작으로 요약할 수 있다.
- 주사위를 굴리는 동작
- 주사위를 굴린 후, 지도에 적혀있는 숫자에 따라서 수를 복사하는 동작
즉, 1.을 위해서, 주사위가 동, 서, 북, 남으로 이동할 때의 동작을 구현하고, 2.를 위해서, 주사위를 굴려, 위치를 이동하고 해당 위치에서 지도의 숫자를 확인하여 문제의 동작을 수행하여야 한다.
풀이
주의할 점은 주사위를 굴리는 동작은 면을 실제로 굴릴 필요가 없고, 항상 맨 위의 눈이 1이라고 생각하고 각 면의 숫자만 바꾸면 된다.
- 주사위 구조체 (
Dice
) - 주사위의 각 면에 적혀있는 수를 저장하는 배열face
와, - 현재 주사위의 위치를 (x
,y
)를 관리한다.
struct Dice {
int face[7]; // 1번 면부터 6번 면까지 적혀있는 숫자
int x;
int y;
};
- 주사위 굴리기 (
RollDice
) - 앞에 언급했듯이, 주사위의 모양이 항상 고정되어있다고 생각한다. 즉, 문제에 적혀있는 대로 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있다. - 주사위를 움직였을 때, 숫자는 다음과 같이 변한다.따라서, 예를 들어 동쪽으로 굴렸다고 하면 1번 면에 4번에 쓰여있던 수를 복사하고, 6번 면에 3번에 쓰여있던 수를 복사하는 식으로 주사위를 굴리는 과정을 구현할 수 있다. 이 때, 마주보는 주사위 눈의 합이 7이라는 것을 이용하면 조금 더 편하게 구현 할 수 있다. (예를 들어, 1번 면에 4번 면에 쓰여 있는 수를 업데이트 하면, 6번 면에 2번 면에 쓰여 있는 수로 업데이트 함)
void rollDice(int dir) {
// 원래 눈에 있던 값들
int d1 = dice.face[1];
int d2 = dice.face[2];
int d3 = dice.face[3];
int d4 = dice.face[4];
int d5 = dice.face[5];
int d6 = dice.face[6];
switch (dir) {
case EAST: {
dice.face[1] = d4;
dice.face[6] = d3;
dice.face[4] = d6;
dice.face[3] = d1;
break;
}
case WEST: {
dice.face[1] = d3;
dice.face[6] = d4;
dice.face[4] = d1;
dice.face[3] = d6;
break;
}
case NORTH: {
dice.face[1] = d5;
dice.face[2] = d1;
dice.face[5] = d6;
dice.face[6] = d2;
break;
}
case SOUTH: {
dice.face[1] = d2;
dice.face[2] = d6;
dice.face[5] = d1;
dice.face[6] = d5;
break;
}
}
}
주의사항
계속 언급하는 거지만, 면을 계속 옮기지말고 면은 고정되었다고 생각하고 숫자만 바꾸는 형식으로 구현한다!
코드
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define X first
#define Y second
using namespace std;
// 주사위의 맨 위의 면은 항상 1이라고 생각하고, 숫자만 갱신한다!
enum Direction { EAST = 1, WEST, NORTH, SOUTH };
struct Dice {
int face[7]; // 1번 면부터 6번 면까지 적혀있는 숫자
int x;
int y;
};
// 동, 서, 북, 남, 1-indexed
const array<int, 5> DX = {0, 0, 0, -1, 1};
const array<int, 5> DY = {0, 1, -1, 0, 0};
int n, m, x, y, k;
vector<vector<int>> game_map;
Dice dice;
void input() {
FASTIO;
// 테스트를 위한 파일 입력 코드 (TODO: 제출 전 삭제)
// freopen("sample_input.txt", "r", stdin);
cin >> n >> m >> x >> y >> k;
game_map.resize(n, vector<int>(m));
dice.x = x;
dice.y = y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> game_map[i][j];
}
}
}
void rollDice(int dir) {
// 원래 눈에 있던 값들
int d1 = dice.face[1];
int d2 = dice.face[2];
int d3 = dice.face[3];
int d4 = dice.face[4];
int d5 = dice.face[5];
int d6 = dice.face[6];
switch (dir) {
case EAST: {
dice.face[1] = d4;
dice.face[6] = d3;
dice.face[4] = d6;
dice.face[3] = d1;
break;
}
case WEST: {
dice.face[1] = d3;
dice.face[6] = d4;
dice.face[4] = d1;
dice.face[3] = d6;
break;
}
case NORTH: {
dice.face[1] = d5;
dice.face[2] = d1;
dice.face[5] = d6;
dice.face[6] = d2;
break;
}
case SOUTH: {
dice.face[1] = d2;
dice.face[2] = d6;
dice.face[5] = d1;
dice.face[6] = d5;
break;
}
}
}
bool isValidRange(pair<int, int> p) {
return 0 <= p.X && p.X < n && 0 <= p.Y && p.Y < m;
}
void solve() {
for (int op = 0; op < k; op++) {
int cmd;
cin >> cmd;
pair<int, int> next = {dice.x + DX[cmd], dice.y + DY[cmd]};
if (isValidRange(next)) {
rollDice(cmd);
dice.x = next.X;
dice.y = next.Y;
if (game_map[next.X][next.Y] == 0) {
// 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다.
game_map[next.X][next.Y] = dice.face[6];
} else {
// 칸에 쓰여 있는 수가 주사위의 바닥 면에 복사되고,
// 칸에 있는 수는 0이 된다.
dice.face[6] = game_map[next.X][next.Y];
game_map[next.X][next.Y] = 0;
}
cout << dice.face[1] << '\n';
}
}
}
int main() {
input();
solve();
return 0;
}
[BOJ 14499] 주사위 굴리기
https://punchdrunkard.github.io/posts/algorithm/boj14499/