[백준] 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 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+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=0 && map[x][y-1]==map[x][y] && scoreMap[x][y-1]==0) { num+=dfs(x,y-1,cur); } if(y+1

결과 화면

from http://nato-blog.tistory.com/145 by ccl(S) rewrite - 2021-11-04 07:02:15