주사위 굴리기2(BJ_G3_23288)

1. 문제 링크

https://www.acmicpc.net/problem/23288

23288번: 주사위 굴리기 2

---

 

2. 나의 코드

메모리: 35716kb
시간: 236ms
코드 길이: 3323B
시간 복잡도 : O(K * (N * M))
설명
- 구현문제
- 주사위를 배열로 표현
- 점수는 BFS로 구하기

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

public class Main {
	// 0 : 오른쪽, 1 : 아래쪽, 2 : 왼쪽, 3 : 위쪽
	static int[] dr = { 0, 1, 0, -1 };
	static int[] dc = { 1, 0, -1, 0 };
	static int N, M, K, result; // 세로, 가로, 이동 횟수, 점수의 합
	static int nowR, nowC, dist; // 현재 R, 현재 C, 이동 방향
	static int[][] dice = { { 0, 2, 0 }, { 4, 1, 3 }, { 0, 5, 0 }, { 0, 6, 0 } };// 주사위 >> 아랫면은 [3][1]
	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());
		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(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < K; i++) move();
		System.out.println(result);
	}

	public static void move() {
		int nr = nowR + dr[dist];
		int nc = nowC + dc[dist];
		int empty = 0;
		// 만약 이동할 수 없는 칸이라면 방향을 반대쪽으로 이동
		if (!isValid(nr, nc)) dist = (dist + 2) % 4;

		// 주사위 변화
		switch (dist) {
		case 0:
			empty = dice[3][1];
			dice[3][1] = dice[1][2];
			dice[1][2] = dice[1][1];
			dice[1][1] = dice[1][0];
			dice[1][0] = empty;
			break;
		case 1:
			empty = dice[3][1];
			dice[3][1] = dice[2][1];
			dice[2][1] = dice[1][1];
			dice[1][1] = dice[0][1];
			dice[0][1] = empty;
			break;
		case 2:
			empty = dice[3][1];
			dice[3][1] = dice[1][0];
			dice[1][0] = dice[1][1];
			dice[1][1] = dice[1][2];
			dice[1][2] = empty;
			break;

		case 3:
			empty = dice[3][1];
			dice[3][1] = dice[0][1];
			dice[0][1] = dice[1][1];
			dice[1][1] = dice[2][1];
			dice[2][1] = empty;
			break;
		}

		// 현재 방향 이동시키기
		nowR = nowR + dr[dist];
		nowC = nowC + dc[dist];
		// 점수 구하기
		result += bfs(nowR, nowC);
		changeDist();
	}

	// bfs로 점수 구하기
	private static int bfs(int r, int c) {
		int count = 1;
		int value = map[r][c];	// value랑 같아야 함
		boolean[][] visited = new boolean[N][M];	// 방문 배열 초기화
		Queue<Point> q = new LinkedList<Point>();
		q.offer(new Point(r, c));
		visited[r][c] = true;	// 방문 체크
		
		while (!q.isEmpty()) {
			Point now = q.poll();
			for (int d = 0; d < 4; d++) {
				int nr = now.x + dr[d];
				int nc = now.y + dc[d];
				
				if (isValid(nr, nc) && !visited[nr][nc] && map[nr][nc] == value) {
					q.offer(new Point(nr, nc));
					++count;
					visited[nr][nc] = true;
				}
			}
		}
		
		return count * value;
	}

	// 주사위가 벗어나는지 여부 확인
	public static boolean isValid(int r, int c) {
		return 0 <= r && r < N && 0 <= c && c < M;
	}
	
	// 방향 변화
	public static void changeDist() {
		int bottom = dice[3][1];
		int now = map[nowR][nowC];
		if (bottom > now) {
			dist = (dist + 1) % 4;
		} else if (bottom < now) {
			if (dist == 0) {
				dist = 3;
			} else {
				dist -= 1;
			}
		} 
	}
}

 

---

 

3. 정답 코드

package study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class Baekjoon23288 {

	static class Dice {
		int r = 0, c = 0;
		int bot = 6, top = 1, north = 2, east = 3, south = 5, west = 4;
		int location = 0;

		public void moveEast() {
			int temp = bot;
			bot = east;
			east = top;
			top = west;
			west = temp;
		}

		public void moveWest() {
			int temp = bot;
			bot = west;
			west = top;
			top = east;
			east = temp;
		}

		public void moveNorth() {
			int temp = bot;
			bot = north;
			north = top;
			top = south;
			south = temp;
		}

		public void moveSouth() {
			int temp = bot;
			bot = south;
			south = top;
			top = north;
			north = temp;
		}

	}

	static int dr[] = { 0, 1, 0, -1 };
	static int dc[] = { 1, 0, -1, 0 };
	static int N, M, ans = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int NMK[] = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int[][] map = new int[NMK[0]][];
		N = NMK[0];
		M = NMK[1];
		for (int i = 0; i < NMK[0]; i++) {
			map[i] = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		}

		Dice dice = new Dice();

		for (int i = 0; i < NMK[2]; i++) {
			move(dice);
			if (dice.bot > map[dice.r][dice.c])
				dice.location = (dice.location + 1) % 4;
			else if (dice.bot < map[dice.r][dice.c])
				dice.location = (dice.location + 3) % 4;
			bfs(dice.r, dice.c, map);
		}
		System.out.println(ans);

	}

	private static void bfs(int r, int c, int map[][]) {
		boolean visited[][] = new boolean[N][M];

		LinkedList<int[]> q = new LinkedList<>();
		visited[r][c] = true;
		q.add(new int[] { r, c });
		int count = 0;

		while (!q.isEmpty()) {
			int[] temp = q.pop();
			++count;
			for (int i = 0; i < 4; i++) {
				int nr = temp[0] + dr[i];
				int nc = temp[1] + dc[i];

				if (nr < 0 || nc < 0 || nr >= N || nc >= M || visited[nr][nc] || map[nr][nc] != map[r][c])
					continue;
				q.add(new int[] { nr, nc });
				visited[nr][nc] = true;
			}
		}
		ans += (count * map[r][c]);
	}

	public static void move(Dice dice) {
		int nr = dice.r + dr[dice.location];
		int nc = dice.c + dc[dice.location];

		if (nr < 0 || nc < 0 || nr >= N || nc >= M) {
			dice.location = (dice.location + 2) % 4;
			move(dice);
			return;
		}

		switch (dice.location) {
		case 0:
			dice.moveEast();
			break;
		case 1:
			dice.moveSouth();
			break;
		case 2:
			dice.moveWest();
			break;
		case 3:
			dice.moveNorth();
			break;
		}
		dice.r = nr;
		dice.c = nc;
	}

}

 

---

 

4. 배운 점

- 주사위 클래스를 만드는 것도 좋은 방법인듯.

- 클래스 내부 함수를 구현하면 뭔가 더 깔끔한 것 같다.