23288. 주사위 굴리기 2

INFO

• 링크: 문제 보러가기
• 언어: Java
• 난이도: 3
• 알고리즘: dfs_bfs 구현 그래프 시뮬레이션
• 소요 시간:

1. 문제 이해

핵심 요구사항

• 주사위를 규칙에 따라 이동해가면서 얻은 점수의 합 구하기
  • 이동: 현재 방향으로 1칸 구른다. (이동할 칸이 없으면 방향을 반대로 바꾼 후 이동)
  • 점수: 도착한 칸의 정수 * 같은 수를 가진 칸의 개수.
  • 회전: 주사위 아랫면($A$)과 칸의 숫자($B$)를 비교해 다음 이동 방향을 정한다.
    • ($A>B$: 시계, $A<B$: 반시계, $A=B$: 유지)

• 신경 써야 건

  • 현재 주사위 바닥면
  • 같은 수를 가진 연결된 칸의 개수
  • 이동 방향 및 주사위 굴리기

• 점수 : 해당 칸의 정수 * 같은 수를 가진 칸의 개수

제한 조건

• 변수 범위
  • 2 ≤ N(세로), M(가로) ≤ 20
  • 1 ≤ K(이동 횟수) ≤ 1,000
  • 1 ≤ 칸의 수 < 10
• 시간: 2초
• 메모리: 1024MB
  • N, M은 작으나, 메모리는 큼.
  • 아마 최적화 신경 쓰지 말고 구현에 집중하라는 의도일 듯?

2. 사고의 흐름 (Thinking)

주사위 굴리는 연산산

• ❌ 1차 시도: 주사위 형태를 그래프 Class로 구현

  • 그래프와 같이 주사위의 각 면을 Node로 만들고 상하좌우 연결관계를 고정하려 함
  • ⇒ 잘못된 생각.
    • 주사위가 굴러갈 때마다 기준 축이 회전하는데, 각 node의 상하좌우가 고정일 것이라고 착각함.
    • 상대적인 위치관계가 계속 변하므로 정적인 그래프 연결로 상태를 표현하기에

• ✅ 2차 시도: 주사위 성질을 이용하여 현재 주사위 형태 배열 구현

  • 주사위의 성질을 파악
    • 마주보는 면의 합 = 7 → 6면 대신, {바닥면, 동쪽면, 남쪽면}의 3개의 축에대한 정보만 있으면 됨
    • 동쪽으로 굴릴 때(dir == 0)
      • 새 바닥 = 기존 동쪽
      • 새 동쪽 = 기존 윗면
      • 새 남쪽 = 기존 남쪽
    • 남쪽으로 굴릴 때(dir == 1)
      • 새 바닥 = 기존 남쪽
      • 새 동쪽 = 기존 동쪽
      • 새 남쪽 = 기존 윗면
    • 서쪽으로 굴릴 때(dir == 2)
      • 새 바닥 = 기존 서쪽
      • 새 동쪽 = 기존 바닥
      • 새 남쪽 = 기존 남쪽
    • 북쪽으로 굴릴 때(dir == 3)
      • 새 바닥 = 기존 북쪽
      • 새 동쪽 = 기존 동쪽
      • 새 남쪽 = 기존 바닥
  • 해당 성질에 맞추어서 roll함수 구현

동일한 값을 가진 인접 타일 개수 세기 (점수 계산용)

• ✅ 1차 시도: dfs 탐색 + dfs memorizing

  • 그래프 탐색을 통해 동일한 값을 가진 인접 타일의 개수를 셈
  • 센 개수를 가지고 다시 한번 동일한 dfs를 돌면서 해당 칸에 적용될 타일 개수 저장해둠 → 변하지 않기 때문.

• ✅ 2차 시도: dfs 탐색 중, 해당하는 좌표 저장 + 저장된 좌표에 값 저장

  • dfs를 두번 도는 건, 매번 dfs를 돌면서 값을 얻는 것보다는 효율적이나, 그럼에도 비효율적임
  • 처음 dfs를 돌때 동일한 값을 가진 인접 타일들의 좌표를 저장하고, dfs가 끝난 후 해당 좌표를 방문하면서 dfs의 결과를 저장.

3. 풀이 및 코드 (Solution)

import java.io.*;
import java.util.*;
 
public class Main {
    static int[][] gp, visited, count;
    static int[] dice = {6,3,5};    // 바닥면, 오른쪽 면, 아래쪽 면
    static int[][] offset = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    static int dir;                 // 0=동 / 1=남 / 2=서 / 3=북
    static int N, M, K;
    static ArrayList<int[]> edit_count;
 
    public static void main(String[] args) throws IOException {
        // get input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        N = Integer.parseInt(temp[0]);
        M = Integer.parseInt(temp[1]);
        K = Integer.parseInt(temp[2]);
 
        // set graph
        gp = new int[N][M];
        visited = new int[N][M];
        count = new int[N][M];
 
        for (int n=0; n<N; n++) {
            temp = br.readLine().split(" ");
            for (int m=0; m<M; m++) {
                gp[n][m] = Integer.parseInt(temp[m]);
            }
        }
 
        // for 0 -> K
        int x = 0, y = 0, score = 0;
        for (int k=0; k<K; k++) {
            // move
            x += offset[dir][0];
            y += offset[dir][1];
 
            // 갈  수 없는 칸일 때
            if (x < 0 || x >= N || y < 0 || y >= M) {
                x -= offset[dir][0];
                y -= offset[dir][1];
                rotateOppo();
                x += offset[dir][0];
                y += offset[dir][1];
            }
 
            // roll
            roll();
 
            // 점수 계산(count or dfs+setCount -> 두번에 나눠서 하는 거 좀 비효율 적임...)
            int adjecanct;
            if (count[x][y] != 0) adjecanct = count[x][y];
            else {
                edit_count = new ArrayList<>();
                adjecanct = dfs(x, y);
                setCount(adjecanct);
            }
            score += adjecanct * gp[x][y];
 
            // rotate
            if (dice[0] > gp[x][y]) rotateCW();
            else if (dice[0] < gp[x][y]) rotateCCW();
        }
        System.out.println(score);
    }
 
    static int dfs(int x, int y) {
        int val = gp[x][y];
        int result = 1; // 자기 자신 포함
        visited[x][y] = 1;
        edit_count.add(new int[] {x, y});
 
        // for 0->4 하면서 상하좌우 탐색
        for (int o=0; o<4; o++) {
            int nx = x+offset[o][0];
            int ny = y+offset[o][1];
 
            // 가능한 경우(경계 안이고, 같은 수를 가졌으며, visit하지 않음)
            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (visited[nx][ny] == 0 && gp[nx][ny] == val){
                    result += dfs(nx, ny);
                    // visited[nx][ny] = 0; -> 경로 찾는게 아니라 그냥 해도 될 것같은데... 안바꾸고.
                }
            }
        }
        return result;
    }
 
    static void setCount(int cnt) {
        for (int[] pos: edit_count) {
            count[pos[0]][pos[1]] = cnt;
        }
    }
 
    static void rotateCW() {
        dir = (dir+1)%4;
    }
 
    static void rotateCCW() {
        dir = (dir+3)%4;
    }
 
    static void rotateOppo() {
        dir = (dir+2)%4;
    }
 
    static void roll( ) {
        int[] new_dice = dice;
 
        switch (dir) {
            case 0:     // 동
                new_dice = new int[] {dice[1], 7 - dice[0], dice[2]};
                break;
            case 1:     // 남
                new_dice = new int[] {dice[2], dice[1], 7 - dice[0]};
                break;
            case 2:     // 서
                new_dice = new int[] {7 - dice[1], dice[0], dice[2]};
                break;
            case 3:     // 북
                new_dice = new int[] {7 - dice[2], dice[1], dice[0]};
                break;
        }
 
        dice = new_dice;
    }
}

• 시간 복잡도: $O(K\times NM)$

  • 각 이동($K$) 마다$N\times M$ 개의 노드에 대해서 그래프 탐색이 진행.
  • 각 노드별로 동서남북 4방향을 체크
  • Memorization을 통해 중복 탐색을 줄였으므로 실제 연산은 더 적음

• Visited 초기화 여부 차이

  • Visited 초기화 안 함: $O(NM)$ → 이번 문제
    • 모든 경로를 찾는 탐색과 다르게 개수를 세기위한 탐색.
    • 한번 접근한 노드는 다시 접근하지 않기 때문에 최악의 경우
  • Visited 초기화 함: $O(3^{NM})$ → 백트래킹
    • 이번문제에서 visited를 초기화 하는 경우 $4\times 3\times 3\times \dots$ 와 같이 총 $N\times M$번 3이 곱해짐
    • 갔던 길을 되돌아 나와서 다른 길을 통해 다시 방문 가능
    • 모든 경로 찾기 → 시간 복잡도 기하급수적으로 늘어남.

4. 회고 (Retrospective)

• 시뮬레이션 문제의 경우 작은 단계로 나누고 순서에 따라 함수 이름을 먼저 적어 놓고, 각 로직을 하나씩 구현하는게 좀 더 안정적인 거 같음.

Computer PS