[백준 Java] 주사위 굴리기 2

문제

---

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

23288번: 주사위 굴리기 2

 

 

 

풀이방법

---

알고리즘을 생각해 내기가 빡세다기보단 구현을 하는게 쉽지 않은 문제였다.

 

bfs는 그냥 같은 숫자를 세어주면 되었기 때문에 구현이 복잡하진 않았다. 문제는 주사위의 방향을 만들어주고, 이에 따라 주사위의 전개도를 바꿔주는 것이 좀 복잡했던 문제였다.

 

주사위 방향을 정하는 코드는 다음과 같다.

시계방향으로 돌릴때는 인덱스에 +1을 더해주었고, 반시계 방향일 때에는 -1을 빼주었다. 값이 음수일때는 4에서 뺀 값을 사용했다.

if(dice[3][1]>map[getx][gety]) {
				index=(index+1)%4; //0,1,2,3 시계방향
				roll(index); //주사위 굴리기
			}
			else if(dice[3][1]<map[getx][gety]) {
				if(index-1<0) {
					index=4-((Math.abs(index-1))%4);//3,2,1,0 반시계방향 (ex)-2넣으면 1)
				}
				else {
				index=(index-1)%4;
				}
				roll(index); //주사위 굴리기
			}
			else {
				roll(index); //주사위 굴리기
			}

roll에서 index를 받아서 해당 방향에 따라 주사위를 굴린다. 내 코드에서는 0이 1북, 1이 동, 2이 남, 3이 서이다.

주사위를 굴릴때는 아래 그림과 같다. 직접 주사위를 굴려보면, 전개도가 어떻게 바뀌어야하는지 알 수 있다.

각각 주사위를 굴리는 코드에는, 범위의 밖으로 나가면 index를 바꿔주고, 반대방향으로 갈 수 있는 코드를 넣어주었다. 

코드

---

 

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

class Node6{
	int x;
	int y;
	public Node6(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

}
public class Main_23288_이서정 {
	static int dice[][]= {{0,2,0},{4,1,3},{0,5,0},{0,6,0}}; //주사위 좌표넣기
	static int del[][]= {{1,0},{-1,0},{0,1},{0,-1}}; //사방탐색 진행
	static int M,N,T;
	static int map[][];
	static int map2[][];
	static boolean visit[][];
	static int getx,gety;
	static int index=1;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N= Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		T=Integer.parseInt(st.nextToken());
		
		map=new int[N][M];
		visit=new boolean[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());
			}
		}
		

		int count=0;
		roll(1); //동쪽부터 실행

		count=bfs(getx,gety); //첫번째 bfs진행
		
		for(int i=1; i<T; i++) {
			if(dice[3][1]>map[getx][gety]) {
				index=(index+1)%4; //0,1,2,3 시계방향
				roll(index); //주사위 굴리기
			}
			else if(dice[3][1]<map[getx][gety]) {
				if(index-1<0) {
					index=4-((Math.abs(index-1))%4);//3,2,1,0 반시계방향 (ex)-2넣으면 1)
				}
				else {
				index=(index-1)%4;
				}
				roll(index); //주사위 굴리기
			}
			else {
				roll(index); //주사위 굴리기
			}
			visit=new boolean[N][M];
			map2=new int[N][M];
			count=count+bfs(getx,gety);
		}
		System.out.println(count);
		
	}
	
	static int bfs(int sx,int sy)
	{
		Queue<Node6> queue= new LinkedList<>();
		queue.offer(new Node6(sx,sy));
		visit[sx][sy]=true;
		
		int count=1;
		int num=0;
		while(!queue.isEmpty()) {
			Node6 temp=queue.poll();
			for(int i=0; i<4; i++) {
				int nx = temp.x+del[i][0];
				int ny = temp.y+del[i][1];
				num=map[temp.x][temp.y];
				
				if(nx>=0 && nx<N && ny>=0 && ny<M && map[nx][ny]==num && visit[nx][ny]==false) { //사방탐색하면서 
					visit[nx][ny]=true; 
					queue.add(new Node6(nx,ny));
					count++; //같은 값들의 개수세기

					
					}
			}
		}
		
		return count*num; //더해야되는 값 리턴
		
	}
	static void roll(int op) {
		if(op==0) {
			up();
		}
		else if(op==1) {
			right();
		}
		else if(op==2) {
			down();
		}
		else if(op==3){
			left();
		}

		
	}
	
	static void up() {
		if(getx-1<0) {
			index=2;
			down();
		}
		else {
			int a=dice[0][1];
			int b=dice[1][1];
			int c=dice[2][1];
			int d=dice[3][1];
			
			dice[0][1]=b;
			dice[1][1]=c;
			dice[2][1]=d;
			dice[3][1]=a;
			getx=getx-1;
		}
	}
	static void right() {
		if(gety+1>=M) {
			index=3;
			left();
		}
		else {
			int a=dice[1][0];
			int b=dice[1][1];
			int c=dice[1][2];
			int d=dice[3][1];
			
			dice[1][0]=d;
			dice[1][1]=a;
			dice[1][2]=b;
			dice[3][1]=c;
			gety=gety+1;
		}
		
	}
	static void down() {
		if(getx+1>=N) {
			index=0;
			up();
		}
		else {
			int a=dice[0][1];
			int b=dice[1][1];
			int c=dice[2][1];
			int d=dice[3][1];
			
			dice[0][1]=d;
			dice[1][1]=a;
			dice[2][1]=b;
			dice[3][1]=c;	
			getx=getx+1;
		}
		
	}
	static void left() {
		if(gety-1<0) {
			index=1;
			right();
		}
		else {
			int a=dice[1][0];
			int b=dice[1][1];
			int c=dice[1][2];
			int d=dice[3][1];
			
			dice[1][0]=b;
			dice[1][1]=c;
			dice[1][2]=d;
			dice[3][1]=a;
			gety=gety-1;
		}
		
	}


}