[백준] 23288. 주사위 굴리기 2 (자바 JAVA)

[ 문제 ]  [백준] 23288. 주사위 굴리기 2 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/23288

23288번: 주사위 굴리기 2

---

# 접근 방법 및 풀이 

 

• 한번에 풀고 너무 속상했던 문제다. 왜 현장에서는 못 풀었을까.. 사실 아이디어를 떠올리지 못했다.
• 주사위 굴리기를 한번 풀어봤음에도 떠올리기가 어려운 아이디어였나보다.
• 아무튼 주사위 굴리기를 풀어본 사람이라면 비교적 쉽게 풀 수 있는 문제다.
• 이 문제의 핵심은 주사위 도면을 이용해서 주사위를 굴렸을 때 바닥면의 주사위 번호가 무엇인지 찾는 것이다.
• dice[4][4] 크기의 이차원 배열을 이용해서 주사위 도면을 이용해서 풀었다. 주사위 도면을 그리면 다음과 같다.

• 	0	1	2	3
  0		2
  1	4	1	3	6
  2		5
  3		6

• 여기서 살펴볼 것은 바닥면표시다. 주사위는 정육면체이므로 도면에 6개만 표현되어야하지만, 바닥면을 맞닿아있는 위아래 양옆으로 다 표시해주었다.
• 즉, 바닥면은 dice[1][3], dice[3][1]이 되는것이다. 
• 여기서 동쪽이나 서쪽으로 구르면, 1행에 있는 가로 줄을 해당 방향으로 한칸씩 이동하면되고

• 	0	1	2	3
  0		2
  1	4	1	3	6
  2		5
  3		6

• 북쪽이나 남쪽으로 구르면, 1열에 세로줄을 해당 방향으로 한칸씩 이동하면 된다.

• 	0	1	2	3
  0		2
  1	4	1	3	6
  2		5
  3		6

• 이때 이동하면 바닥면의 주사위 번호가 바뀌므로 dice[1][3]의 값과 dice[3][1] 의 값을 동일하게 변경해주면 된다.
• 이후 점수획득은 bfs로, 다음으로 이동할 방향 또한 문제의 조건에 맞게 변경시켜주면 된다.
• 자세한건 코드참조

 

 

# 주의할 점 

 

• 주사위 도면을 떠올리면서 바닥면을 어떻게 변경할지 생각하기

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj23288_주사위굴리기2 {
	static int N, M, K, map[][], ans = 0, moveDir, r, c;
	static int dr[] = { -1, 0, 1, 0 };
	static int dc[] = { 0, 1, 0, -1 };
	static int dice[][] = {
			{ 0, 2, 0, 0 },
			{ 4, 1, 3, 6 },
			{ 0, 5, 0, 0 },
			{ 0, 6, 0, 0 } };

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		moveDir = 1;
		r = 0;
		c = 0;
		for (int i = 0; i < K; i++) {
			move();
		}
		System.out.println(ans);
	}

	private static void move() {
		// 움직여
		int nr = r + dr[moveDir];
		int nc = c + dc[moveDir];
		if (nr < 0 || nc < 0 || nr >= N || nc >= M) {
			moveDir = (moveDir + 2) % 4;
			nr = r + dr[moveDir];
			nc = c + dc[moveDir];
		}
		r = nr;
		c = nc;
		if (moveDir == 0) { // 상
			int tmp = dice[0][1];
			for (int i = 0; i < 3; i++) {
				dice[i][1] = dice[i + 1][1];
			}
			dice[3][1] = tmp;
			dice[1][3] = dice[3][1];
		} else if (moveDir == 1) {// 우
			int tmp = dice[1][3];
			for(int j = 3; j > 0; j--) {
				dice[1][j] = dice[1][j-1];
			}
			dice[1][0] = tmp;
			dice[3][1] = dice[1][3];
		} else if (moveDir == 2) {// 하
			int tmp = dice[3][1];
			for (int i = 3; i > 0; i--) {
				dice[i][1] = dice[i - 1][1];
			}
			dice[0][1] = tmp;
			dice[1][3] = dice[3][1];
		} else {// 좌
			int tmp = dice[1][0];
			for(int j = 0; j < 3; j++) {
				dice[1][j] = dice[1][j+1];
			}
			dice[1][3] = tmp;
			dice[3][1] = dice[1][3];
		}

		// 점수 획득
		ans += getScores();
		// 다음에 갈 방향과 위치 정해
		int A = dice[1][3];
		int B = map[r][c];
		if(A > B) {
			moveDir = (moveDir+1) % 4;
		}else if(A < B) {
			moveDir = (moveDir-1 < 0)? 3 : moveDir-1;
		}
	}

	private static int getScores() {
		int B = map[r][c];
		int C = 0;
		boolean visit[][] = new boolean[N][M];
		visit[r][c] = true;
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(r, c));
		while (!queue.isEmpty()) {
			Point p = queue.poll();
			C++;
			for (int d = 0; d < 4; d++) {
				int nr = p.x + dr[d];
				int nc = p.y + dc[d];
				if (nr < 0 || nc < 0 || nr >= N || nc >= M || visit[nr][nc] || map[nr][nc] != B)
					continue;
				visit[nr][nc] = true;
				queue.add(new Point(nr, nc));
			}
		}
		return B * C;
	}
}

 

 

 

REVIEW

최근에 잘 못 풀던 문제를 다시 차근히 접근해서 푸는 중이다.

깡 구현은 진짜 매일 하나씩 풀어야겠다. 그래야 감을 유지하는 것 같다.