Java/코딩테스트
백준 23288
Bubbles
2023. 10. 13. 20:04
🎲 백준 23288 주사위 굴리기 2
https://www.acmicpc.net/problem/23288
23288번: 주사위 굴리기 2
크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼
www.acmicpc.net
🎲 어릴때부터 이런 입체도형 계산하는 문제를 유구하게 못했는데 ..주사위 돌아가는거 생각하는게 헷갈렸다ㅎ
🎲 주사위 돌아가는 부분을 이 블로그를 보고 힌트를 얻었다.
🎲 주사위
🎲 주사위 자체를 현재 방향에 따라 위 이미지처럼 계속 돌려가면서, 아랫면 (dice[3][1]) 만 점수 비교하는데 쓰면 된다.
🎲 자료구조
private static int row, col, move, answer, currentDir;
private static Pos curPos;
private static int[] dirX = { 0, 1, 0, -1};
private static int[] dirY = { 1, 0, -1, 0};
private static int[][] dice = {
{0, 2, 0},
{4, 1, 3},
{0, 5, 0},
{0, 6, 0}
};
private static int[][] map;🎲 메인 로직
🎲 firstMove : 현재 위치에서 방향 결정한 다음 이동.
- nextX, nextY 찾아서 이동시키고, 방향(currentDir)도 유효하지 않은 방향이면 뒤집어주기
- 그 후, nextX, nextY 기준으로 getScore(), findNextDir() 호출하기
private static void firstMove() {
int nextX = curPos.x + dirX[currentDir];
int nextY = curPos.y + dirY[currentDir];
if (!isValid(nextX, nextY)) {
nextX = curPos.x + dirX[(currentDir + 2) % 4];
nextY = curPos.y + dirY[(currentDir + 2) % 4];
currentDir = (currentDir + 2) % 4;
}
curPos = new Pos(nextX, nextY);
getScore(nextX, nextY);
findNextDir(nextX, nextY);
}
🎲 getScore() : 해당 좌표의 점수, 그리고 findLen 함수 호출을 통해 갈 수 있는 칸 수 계산한다음 해당 칸에서의 점수 계산하기
private static void getScore(int x, int y) {
int score = map[x][y];
int len = findLen(x, y, score);
answer += score * len;
}
🎲 findLen() : BFS 방식 구현
- 헷갈렸던게 갈 수 있는 경로라고 생각했는데, 이동할 수 있는 칸의 개수를 세는 것이다.
- 경로라 생각하고 DFS로 하면 중간 테스트 케이스 틀리는 게 생긴다.
- 종단점이 있는게 아니고 연결된 블록 찾는거라 BFS가 문제 취지에 더 맞을 것 같다.
private static int findLen(int x, int y, int score) {
boolean[][] temp = new boolean[row][col];
int len = 0;
Queue<Pos> queue = new LinkedList<>();
queue.add(new Pos(x, y));
temp[x][y] = true;
while (!queue.isEmpty()) {
Pos pop = queue.poll();
len++;
for (int i = 0; i < 4; i++) {
int nextX = pop.x + dirX[i];
int nextY = pop.y + dirY[i];
if (!isValid(nextX, nextY)) {
continue;
}
if (map[nextX][nextY] != score) {
continue;
}
if (temp[nextX][nextY]) {
continue;
}
queue.add(new Pos(nextX, nextY));
temp[nextX][nextY] = true;
}
}
return len;
}
🎲 findNextDir() : 다음 방향을 찾는다.
- 여기서 맨 처음 그린 주사위 계산 작업이 나온다.
- 현재 방향에 맞게 주사위 아랫면을 계산해주고, map에 있는 score와 비교하여 방향을 재조정해준다.
private static void findNextDir(int x, int y) {
// 현재 주사위 아랫면 구하기
switch (currentDir) {
case 0 :
int temp = dice[1][2];
dice[1][2] = dice[1][1];
dice[1][1] = dice[1][0];
dice[1][0] = dice[3][1];
dice[3][1] = temp;
break;
case 1 :
temp = dice[3][1];
dice[3][1] = dice[2][1];
dice[2][1] = dice[1][1];
dice[1][1] = dice[0][1];
dice[0][1] = temp;
break;
case 2 :
temp = dice[1][0];
dice[1][0] = dice[1][1];
dice[1][1] = dice[1][2];
dice[1][2] = dice[3][1];
dice[3][1] = temp;
break;
case 3 :
temp = dice[0][1];
dice[0][1] = dice[1][1];
dice[1][1] = dice[2][1];
dice[2][1] = dice[3][1];
dice[3][1] = temp;
break;
}
int a = dice[3][1];
if (a > map[x][y]) {
currentDir = (currentDir + 1) % 4;
} else if (a < map[x][y]) {
currentDir = (currentDir + 3) % 4;
}
}
🎲 전체코드
import java.util.*;
import java.io.*;
public class p23288 {
private static int row, col, move, answer, currentDir;
private static Pos curPos;
private static int[] dirX = { 0, 1, 0, -1};
private static int[] dirY = { 1, 0, -1, 0};
private static int[][] dice = {
{0, 2, 0},
{4, 1, 3},
{0, 5, 0},
{0, 6, 0}
};
private static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
row = Integer.parseInt(st.nextToken());
col = Integer.parseInt(st.nextToken());
move = Integer.parseInt(st.nextToken());
answer = currentDir = 0;
map = new int[row][col];
for (int i = 0; i < row; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
curPos = new Pos(0,0 );
for (int i = 0; i < move; i++) {
firstMove();
}
System.out.println(answer);
}
private static void firstMove() {
int nextX = curPos.x + dirX[currentDir];
int nextY = curPos.y + dirY[currentDir];
if (!isValid(nextX, nextY)) {
nextX = curPos.x + dirX[(currentDir + 2) % 4];
nextY = curPos.y + dirY[(currentDir + 2) % 4];
currentDir = (currentDir + 2) % 4;
}
curPos = new Pos(nextX, nextY);
getScore(nextX, nextY);
findNextDir(nextX, nextY);
}
private static void findNextDir(int x, int y) {
// 현재 주사위 아랫면 구하기
switch (currentDir) {
case 0 :
int temp = dice[1][2];
dice[1][2] = dice[1][1];
dice[1][1] = dice[1][0];
dice[1][0] = dice[3][1];
dice[3][1] = temp;
break;
case 1 :
temp = dice[3][1];
dice[3][1] = dice[2][1];
dice[2][1] = dice[1][1];
dice[1][1] = dice[0][1];
dice[0][1] = temp;
break;
case 2 :
temp = dice[1][0];
dice[1][0] = dice[1][1];
dice[1][1] = dice[1][2];
dice[1][2] = dice[3][1];
dice[3][1] = temp;
break;
case 3 :
temp = dice[0][1];
dice[0][1] = dice[1][1];
dice[1][1] = dice[2][1];
dice[2][1] = dice[3][1];
dice[3][1] = temp;
break;
}
int a = dice[3][1];
if (a > map[x][y]) {
currentDir = (currentDir + 1) % 4;
} else if (a < map[x][y]) {
currentDir = (currentDir + 3) % 4;
}
}
private static void getScore(int x, int y) {
int score = map[x][y];
int len = findLen(x, y, score);
answer += score * len;
}
private static int findLen(int x, int y, int score) {
boolean[][] temp = new boolean[row][col];
int len = 0;
Queue<Pos> queue = new LinkedList<>();
queue.add(new Pos(x, y));
temp[x][y] = true;
while (!queue.isEmpty()) {
Pos pop = queue.poll();
len++;
for (int i = 0; i < 4; i++) {
int nextX = pop.x + dirX[i];
int nextY = pop.y + dirY[i];
if (!isValid(nextX, nextY)) {
continue;
}
if (map[nextX][nextY] != score) {
continue;
}
if (temp[nextX][nextY]) {
continue;
}
queue.add(new Pos(nextX, nextY));
temp[nextX][nextY] = true;
}
}
return len;
}
private static boolean isValid(int x, int y) {
if (x < 0 || x >= row || y < 0 || y >= col) {
return false;
}
return true;
}
private static class Pos {
int x;
int y;
Pos (int x, int y) {
this.x = x;
this.y = y;
}
}
}