[백준] 23288 - 주사위 굴리기 2

[문제링크]

23288번: 주사위 굴리기 2

 

0. 구현 / 그래프 탐색 문제

 

1. 각 지점의 값 * 같은 값으로 연결된 지점의 수 = 해당 지점의 점수 이므로, 사전에 DFS를 진행해 scoreMap을 제작한다

 

2. dice의 방향은 동-남-서-북 순서로 정의, 2칸 차이나면 반대 방향이고, +1로 진행시 시계방향, -1로 진행시 반시계방향

 

3. 문제 정의대로 dice를 움직인다

• 이동 가능 판단, 불가시 방향 반대로 전환
• 해당 방향으로 1칸 이동 (roll 함수 이용), 점수 누적
• map의 값과 dice값 비교를 통해 방향 전

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	static int[] dice;
	static int[][] dir = {
			{0,1},{1,0},{0,-1},{-1,0}//시계방향 동남서북
	};
	static int[][]scoreMap;
	static int[][]map;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		dice = new int[] {1, 3, 6, 4, 2, 5};//앞 오 바닥 왼 위 아래
		int x=0,y=0;//init pos 0,0
		int curDir=0;//east
		
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int k = pint(st.nextToken());
		
		map = new int[n][m];
		scoreMap = new int[n][m];
		List<Integer> list = new ArrayList<>();
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				map[i][j]=pint(st.nextToken());
			}
		}
		
		//1. scoremap에 연속된 갯수 구하기
		int cnt=1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(scoreMap[i][j]==0) {
					int curV=dfs(i,j,cnt++);
					list.add(curV);
				}
			}
		}
		//2. map의 값으로 곱, 최종 칸 당 점수 구하기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scoreMap[i][j] = list.get(scoreMap[i][j]-1);
				scoreMap[i][j] *=map[i][j];
			}
		}
		
		//3. 주사위 go
		int scoreSum=0;
		for (int i = 0; i < k; i++) {
			//한칸 굴러간다
			int nextX = x+dir[curDir][0];
			int nextY = y+dir[curDir][1];
			//못가면 반대로 굴러간다
			if(nextX<0 || nextX>=n || nextY<0 || nextY>=m) {
				curDir = (curDir+2)%4;
				nextX = x+dir[curDir][0];
				nextY = y+dir[curDir][1];
			}
			x=nextX;y=nextY;
			//해당 방향으로 구르기
			roll(curDir);
			
			//점수먹기
			scoreSum += scoreMap[x][y];
			//방향바꾸기
			//바닥면 = dice[2]
			if(map[x][y]<dice[2]) {
				//밑면이 더 크면 시계방향
				curDir= (curDir+1)%4;
			}
			else if(map[x][y]>dice[2]) {
				//밑면이 더 작으면 반시계방향
				curDir= (curDir+4-1)%4;
			}
			else {
				//do nothing
			}
		}
		System.out.println(scoreSum);
	}
	static void roll(int curDir) {
		int tmp;
		//앞 오 바닥 왼 위 아래
		//east
		if(curDir==0) {
			roll(2);
			roll(2);
			roll(2);
		}
		//south
		else if(curDir==1) {
			tmp = dice[0];
			dice[0]=dice[4];
			dice[4]=dice[2];
			dice[2]=dice[5];
			dice[5]=tmp;
		}
		//west
		else if(curDir==2) {
			tmp = dice[0];
			dice[0]=dice[1];
			dice[1]=dice[2];
			dice[2]=dice[3];
			dice[3]=tmp;
		}
		//north
		else if(curDir==3) {
			roll(1);
			roll(1);
			roll(1);
		}
		
	}
	static int dfs(int x, int y, int cur) {
		int num=1;
		scoreMap[x][y]=cur;
		
		if(x-1>=0 && map[x-1][y]==map[x][y] && scoreMap[x-1][y]==0) {
			num+=dfs(x-1,y,cur);
		}
		if(x+1<map.length && map[x+1][y]==map[x][y] && scoreMap[x+1][y]==0) {
			num+=dfs(x+1,y,cur);
		}
		if(y-1>=0 && map[x][y-1]==map[x][y] && scoreMap[x][y-1]==0) {
			num+=dfs(x,y-1,cur);
		}
		if(y+1<map[0].length && map[x][y+1]==map[x][y] && scoreMap[x][y+1]==0) {
			num+=dfs(x,y+1,cur);
		}
		
		return num;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면