[ Baekjoon - 10/09 ] - 23288번: 주사위 굴리기 2

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

23288번: 주사위 굴리기 2

 

• 소요 시간 : 최적화 시간까지 합치면 4시간.. 어후

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 1024MB
   • 문제
     • NxM의 지도(2≤N,M≤20), 이동횟수 K(1≤K≤1,000)
     • 주사위를 (1,1)부터 K번만큼 [문제에서 주어진 조건에 따라 방향을 정하고, 해당방향으로 한칸 이동하여(해당 방향으로 주사위가 넘어지게 함) 주사위를 이동한 뒤, 해당 지점으로부터 갈수있는(현재 좌표의 지도에 적힌 점수와 같은구역이 근처에 있다면 가능) 곳의 수를 세어 점수*영역의 수를 합산] 하는 과정을 반복하여 최종적으로 얻은 점수를 출력하는 문제
     • 방향을 정하는 조건은, 주사위의 밑면을 A, 해당 좌표의 지도 값을 B라 할때
       1. A>B이면, 현재 방향에서 시계방향 회전 (북 -> 동 -> 남 -> 서 -> 북)
       2. A<B이면, 현재 방향에서 시계 반대방향 회전 (북 -> 서 -> 남 -> 동 -> 북)
       3. 예외적으로, 한번 움직였을 때(주사위가 해당방향으로 넘어졌을 때) 맵밖에 나갈 방향이라면 반대방향으로 바꿔야 한다.
   • 이해
     • 문제도 워낙 길고, 설명도 난해해서 입출력 예제를 따라가며 그려보았다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 문제부터가 우선 많이 난해했다. 그 중에서도 제일 설명이 필요했던건, 주사위도 같이 방향을 바꾸며 바닥을 끌며 진행하는건지.. 아니면 그대로 엎어지는 식으로 진행하는지 자세히 나와있지 않아서 바로 입출력예제로 접근했다. (정말 지양하는 접근인데ㅠ )
   • 사실 문제에서도 입력예제 1~7은 같은 지도에서 횟수만 증가시키는 방식으로 구성되어있다고 친절하게 적어주었지만.. 문제를 속독하고 바로 예제로 들어갔어서 왜 이동구역이 내가 생각한 바와 다른지 오랜시간 고민했다..
   • 입력예제 1번의 경우 이동횟수가 1이라서 한번만 이동하고 바로 점수를 구한 그림이었는데, 나는 색칠한 부분이 점수를 구한그림이 아닌 결과적으로 나아갈 수 있는 구역이라 생각해서 오랜시간 고민했고.. 결국 스터디원에게 물어본후에야 잘못된 접근을 하고있었다는걸 깨달았다ㅠ (이동횟수 K가 왜 안보였을까...)
   •  위 시도를 거친후에야 문제를 제대로 이해할수있었고 바로 알고리즘을 생각했던것 같다.
   • X친 부분은 이동횟수가 1이라 괜히적었다 싶어서 X로 표시한건데 이후 입출력예제는 이동횟수만 증가한 Map이라 결과적으로는 필요한 부분이었다 ㅋㅋ
3. 문제를 어떻게 해결할 것인가

   • 

   • 1st 접근 - 주사위를 어떻게 표현해야 하나..)
     • 우선 주사위를 어떻게 코드적으로 풀어내야할지 많은 고민을 했다.
     • 주사위의 특징에 대해 생각해보았는데, 밑 3가지 정도 나왔다.
       1. 6개의 면을가진 육면체이다.
       2. 마주보는 면의 숫자 합은 7 이다.
       3. 주사위를 굴리면 옆면(좌측,우측)은 그대로 옆면에 위치하고 4개의 수만 회전한다.
     • 3번 특징을 이용하면 주사위를 표현할수 있을것 같아서, 위 사진의 왼쪽 그림을 그려보았다.
     • 각 앞으로, 좌측으로, 우측으로, 뒤로 주사위가 회전했을때 칸과 닿는 수를 적어보았는데,
       우/좌측의 경우 6,3,1,4,...가 반복되었고
       위/아래의 경우 6,5,1,2... 가 반복되었다.
     • 주사위는 총 6개의 면이므로 서로다른 숫자가 6개인데, 우/좌측 4개, 위/아래 4개여서 어떤 숫자가 겹치는지 그려보니 우선 가장 밑의 면과 가장 위의면이 겹치는것을 확인할 수 있었다.
     • 이를 그림으로 나타낸 것이 화살표로 가르킨 십자가(?) 모양이다.
     • 밑면이 6이아닌 다른 값으로 바뀌었을때 어떻게 이동하는지 분석해보니 우/좌측일때는 같은 행안에서 숫자가 한칸씩 밀렸고, 위/아래의 경우 같은 열 안에서 숫자가 한칸씩 밀리는 형태였다.
     • 즉, temp변수를 하나 선언해서 끝값을 저장하고, 숫자를 한칸씩 민 뒤에 temp를 빈곳에 넣어주면 충분히 회전하는 주사위의 현재상태를 저장할 수 있을것 같았다!
   • 2nd 접근 - 구현의 큰틀 잡기)
     • 점수를 계산할때는 인접한 애들중에 같은 수를 찾으면 되므로 BFS와 DFS둘다 구현 가능해보였고, 방향을 정하고 이동하는 것도 어짜피 한칸씩 이동하는 것이므로 BFS, DFS둘다 가능하다 생각했다.
     • 문제에서 주어진 반복부분대로 이동횟수(K)만큼 반복하는데, 큰틀은 아래와 같다.
       1. 이동할 곳이 맵안이 아니라면 반대방향으로 이동하여 맵 안에서 이동할 수 있는 좌표로 만들고 이동.
       2. 해당 좌표로 부터 점수를 얻을 수 있는 구역을 탐색하여 점수를 누적한다.
       3. 좌표를 이동했으니 B를 알수있고, 주사위도 해당 방향으로 움직여 A를 알수 있다.
       4. 문제에서 주어진 A,B 관계에 따라 [시계 / 반시계 / 방향그대로] 를 결정한다
     • 이렇게 구현할 수 있다. 사실 굉장히 간단한 것처럼 풀어썼지만.. 최적화 시키기까지 꽤 오랜시간이 걸렸다ㅠ
     • 후에 꼭 다시 풀어봐야할것같다.
4. 위 계획을 검증
   • 문제 자체는 조건만 잘 지키면 되는 완탐이라 크게 다루진 않겠다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static int N,M,K;
            static int[] dx = {0, 1, 0, -1};
            static int[] dy = {1, 0, -1, 0};
            static int[][] map;
            static int[][] dice
                    = {{0,2,0,0},   //  0  뒤  0  0
                    {4,1,3,6},      // 좌측 위 우측 밑
                    {0,5,0,0},      //  0  앞  0  0
                    {0,6,0,0}};     //  0  밑  0  0
            static boolean[][] vis;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                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 n = 0; n < N; n++) {
                    st = new StringTokenizer(br.readLine());
                    for (int m = 0; m < M; m++) {
                        map[n][m] = Integer.parseInt(st.nextToken());
                    }
                }
        
                int x = 0;
                int y = 0;
                int d = 0;
                int ans = 0;
                // 이동횟수만큼만 이동
                while (K-- > 0) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    // 맵안이 아니라면
                    if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
                        // 방향 바꿔줘야함 : [0은 상, 1은 우, 2는 하, 3은 좌] 이므로 반대방향과 2차이
                        d = (d + 2) % 4;
                        nx = x + dx[d];
                        ny = y + dy[d];
                    }
                    moveDice(dice, d);
        
                    vis = new boolean[N][M];
                    vis[nx][ny] = true;
                    int cnt = dfs(nx, ny, map[nx][ny]);
                    ans += cnt * map[nx][ny];
        
                    int A = dice[3][1]; // 주사위의 밑면
                    int B = map[nx][ny]; // 해당 위치의 점수
        
                    // A>B이면 시계방향
                    if (A > B) {
                        d = (d + 1) % 4;
                    }
                    // A<B이면 반시계방향
                    else if (A < B) {
                        d = (d + 3) % 4;
                    }
        
                    x = nx;
                    y = ny;
                }
                System.out.println(ans);
            }
        
            private static int dfs(int x, int y, int num) {
                int cnt = 1;
                // 1. 연결되어있는가
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    // 2-1. 갈수있는가 - 맵 안
                    if (0<=nx && nx<N && 0<=ny && ny<M && !vis[nx][ny]) {
                        // 2-2. 갈수있는가 - 같은 값
                        if(map[nx][ny] == num){
                            vis[nx][ny] = true;
                            cnt += dfs(nx, ny, num);
                        }
                    }
                }
                return cnt;
            }
        
            private static void moveDice(int[][] dice, int direction) {
                int tmp=0;
                switch (direction) {
                    case 0: // 동 -> dice[1][]을 한칸씩 좌측으로 옮기고 가장 좌측의 아이를 우측에 넣음
                        tmp = dice[1][3];
                        for (int i = 3; i > 0; i--) {
                            dice[1][i] = dice[1][i - 1];
                        }
                        dice[1][0] = tmp;
                        dice[3][1] = dice[1][3];
                        break;
        
                    case 1 : // 서 -> dice[1][]을 한칸씩 우측으로 옮기고 가장 우측의 아이를 좌측에 넣음
                        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];
                        break;
                    case 2 : // 남 -> dice[][1]을 한칸씩 위로 옮기고 가장 위의 아이를 밑에 넣음
                        tmp = dice[1][0];
                        for (int i = 0; i < 3; i++) {
                            dice[1][i] = dice[1][i + 1];
                        }
                        dice[1][3] = tmp;
                        dice[3][1] = dice[1][3];
                        break;
                    case 3 : // 북 -> dice[][1]을 한칸씩 밑으로 옮기고 가장 밑의 아이를 위에 넣음
                        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];
                        break;
                }
            }
        }

   2. Python 3

      • import sys
        
        dxy = [[0,1],[1,0],[0,-1],[-1,0]]
        
        dice = \
            [[0,2,0,0],     #  0  뒤  0  0
             [4,1,3,6],     # 좌측 위 우측 밑
             [0,5,0,0],     #  0  앞  0  0
             [0,6,0,0]]     #  0  밑  0  0
        
        N,M,K = map(int, sys.stdin.readline().split())
        graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
        
        def moveDice(d):
            if d==0: # 동 -> dice[1][]을 한칸씩 좌측으로 옮기고 가장 좌측의 아이를 우측에 넣음
                tmp = dice[1][3]
                for i in range(3,0,-1):
                    dice[1][i] = dice[1][i-1]
                dice[1][0] = tmp
                dice[3][1] = dice[1][3]
            elif d==1: # 서 -> dice[1][]을 한칸씩 우측으로 옮기고 가장 우측의 아이를 좌측에 넣음
                tmp = dice[3][1]
                for i in range(3,0,-1):
                    dice[i][1] = dice[i - 1][1]
                dice[0][1] = tmp
                dice[1][3] = dice[3][1]
            elif d==2: # 남 -> dice[][1]을 한칸씩 위로 옮기고 가장 위의 아이를 밑에 넣음
                tmp = dice[1][0]
                for i in range(0,3):
                    dice[1][i] = dice[1][i + 1]
                dice[1][3] = tmp
                dice[3][1] = dice[1][3]
            elif d==3: # 북 -> dice[][1]을 한칸씩 밑으로 옮기고 가장 밑의 아이를 위에 넣음
                tmp = dice[0][1]
                for i in range(0,3):
                    dice[i][1] = dice[i + 1][1]
                dice[3][1] = tmp
                dice[1][3] = dice[3][1]
        
        def dfs(x, y, num):
            cnt = 1
            # 1. 연결되어있는가
            for i in range(4):
                nx = x+dxy[i][0]
                ny = y+dxy[i][1]
                #  2-1. 갈수있는가 - 맵 안
                if 0<=nx<N and 0<=ny<M:
                    # 2-2. 갈수있는가 - 같은 값
                    if not vis[nx][ny] and graph[nx][ny] == num:
                        vis[nx][ny] = True
                        cnt += dfs(nx,ny,num)
            return cnt
        
        
        x=0
        y=0
        d=0
        ans=0
        
        # 이동횟수만큼만 이동
        for k in range(K):
            nx = x+dxy[d][0]
            ny = y+dxy[d][1]
        
            # 맵안이 아니라면
            if nx<0 or nx>=N or ny<0 or ny>=M:
                # 방향 바꿔줘야함 : [0은 상, 1은 우, 2는 하, 3은 좌] 이므로 반대방향과 2차이
                d = (d+2)%4
                nx = x + dxy[d][0]
                ny = y + dxy[d][1]
        
            moveDice(d)
        
            vis = [[False for _ in range(M)] for _ in range(N)]
            vis[nx][ny] = True
            cnt = dfs(nx,ny,graph[nx][ny])
            ans += cnt * graph[nx][ny]
        
            A = dice[3][1] # 주사위의 밑면
            B = graph[nx][ny] # 해당 위치의 점수
        
            # A>B이면 시계방향
            if A>B:
                d = (d+1)%4
            # A<B이면 반시계방향
            elif A<B:
                d = (d+3)%4
        
            x = nx
            y = ny
        
        print(ans)

 

 

• 결과 - Java 11

컴파일에러... 인텔리제이가 switch-case문 그렇게 쓰는거 아니라고 간단화 시킬수있다해서 믿고 냈는데 Java11에 그런거 없다는 에러가 나왔다.. 내 인텔리제이는 도대체 버전이 뭐인거지?

// 처음에 쓴 방법
switch(d){
	case 1:
		System.out.println("예시");
    	break;
}

// 인텔리제이가 바꾸라한 방법 - 얘는 버전이 뭘까... 오히려 신버전인가
switch(d){
	case 1 -> {
		System.out.println("예시");
    }
}

• 결과 - Python 3