문제 링크

문제 파악

지구와 달 사이 공간의 행렬 N x M (2≤ N, M ≤ 6)에서 달 여행에 필요한 최소 연료 값을 출력하라

• 같은 방향으로 두 번 이동할 수 없다.

접근 방법

1. dfs에서 y가 7(높이)이되면 pq에 넣어 가장 적은 비용을 출력한다.
2. dp는 dp[i][j] i 행 j 열이 = dp[i-1][j-1 or j or j+1] + dp[i][j]

1. 같은 방향인지 확인하기 위해 dir를 노드에 추가하고, 이전과 같은 dir면 멈추는 조건을 추가해야 한다.

2. 재귀에서 탈출했을 때 visited false 처리

• 재귀는 stack처럼 동작하기 때문에 달을 찍고 return하면 두번째 뒤 점에서 다시 달까지 시도

코드 구현

import java.util.*;

public class Main {
    public static class Node {
        int x;
        int y;
        int v;
        int dir; // 0, 1, 2 (좌하, 하, 우하)

        public Node(int x, int y, int v, int dir) {
            this.x = x;
            this.y = y;
            this.v = v;
            this.dir = dir;
        }

    }

    public static boolean[][] v;
    public static PriorityQueue<Integer> pq;
    public static int[][] coord;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        coord = new int[n][m];

        // 행렬 생성
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int a = sc.nextInt();
                coord[i][j] = a;
            }
        }

        // 달에 도달한 노드 저장소
        pq = new PriorityQueue<>((a, b) -> a - b);

        // 첫 번째 행 모든 열에서 출발점 생성 후 dfs
        for (int i = 0; i < m; i++) {
            int value = coord[0][i];

            v = new boolean[n][m];

            v[0][i] = true;
            dfs(new Node(i, 0,  value, 3)); // 첫 direction은 겹치지 않도록 [0, 2]가 아닌 값
        }


        System.out.println(pq.peek());
    }

    public static void dfs(Node cur) {
        // 좌, 하, 우
        int[] dx = {-1, 0, 1};
        int[] dy = {1, 1, 1};

        // 달에 닿으면 pq에 넣기
        // 아래로만 이동하기 때문에 depth가 필요없음
        if (cur.y == coord.length-1) {
            pq.add(cur.v);
            return;
        }

        for (int j = 0; j < 3; j++) {
            int x = cur.x + dx[j];
            int y = cur.y + dy[j];

            if (x >= 0 && y >= 0 && y < coord.length && x < coord[0].length) {
                if (v[y][x] || cur.dir == j) continue;

                v[y][x] = true;
                dfs(new Node(x, y, cur.v + coord[y][x], j));
                v[y][x] = false;
            }
        }
    }
}

배우게 된 점

1. 출발점에서 visited 초기화해주니까 재귀 탈출해서 v[y][x] = false 처리가 필요없는 줄 알았다. 

2.  x, y가 col, row라 헷갈려서 잘못썼다.

질문

dp코드도 봐야겠다 복잡해보임 ㅠ

https://velog.io/@gkdbssla97/BOJ-17484.-%EC%A7%84%EC%9A%B0%EC%9D%98-%EB%8B%AC-%EC%97%AC%ED%96%89-Small-Java