99클럽 코테 스터디 14일차 TIL - 진우의 달 여행 (Small)

오늘의 학습 키워드

• 다익스트라 알고리즘 변형
• 우선순위 큐(PriorityQueue)
• 방향 제한 탐

---

공부한 내용 정리

이번 문제는 기본적으로 최단 경로를 찾는 문제와 유사했지만, 같은 방향으로 연속 이동할 수 없다는 조건이 추가되어 있었습니다.

따라서 단순한 다익스트라 알고리즘이 아니라, 현재까지 누적 연료량 + 이전에 움직인 방향까지 상태로 관리해야 했습니다.

주요 아이디어는 다음과 같았습니다.

• (x, y) 위치에 도착했을 때, 이전 이동 방향을 함께 저장합니다.
• 다음에 이동할 때, 직전 이동 방향과 같으면 이동하지 않습니다.
• 첫 번째 줄의 모든 칸에서 출발할 수 있으며, N-1번째 줄(마지막 줄)에 도달하면 바로 최소 연료를 출력합니다.

---

소스코드

/*
진우의 달 여행
입력: 행렬 N, M
    다음 N 줄동안 각 행렬의 원소 값이 주어짐
조건: 우주선은 대각선 아래, 아래, 대각선 오른쪽 으로만 이동가능
    이전에 움직 였던 방향으로 움직일 수 없음.
    즉, 같은 방향으로 2번 움직이면 안됨.
    최소 거리로 달에서 지구까지 갈 수 있는 방법의 수
로직: N이 index가 5까지 가야됨 그럼 지구 도착
    최소 거리로 달에서 지구까지 갈 수 있는 방법의 수
    
출력: 최소 연료의 값
*/
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] board = new int[N][M];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 이동 방향: 왼쪽 아래, 아래, 오른쪽 아래
        int[] dx = {1, 1, 1};
        int[] dy = {-1, 0, 1};
        
        // PriorityQueue: {x, y, fuel, previous_direction}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        
        // 첫 줄의 모든 위치에서 시작 가능
        for(int j = 0; j < M; j++) {
            pq.add(new int[]{0, j, board[0][j], -1});
        }
        
        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0];
            int y = cur[1];
            int fuel = cur[2];
            int prevDir = cur[3];
            
            // 달에 도착
            if(x == N-1) {
                System.out.println(fuel);
                return;
            }
            
            // 3가지 방향으로 이동
            for(int dir = 0; dir < 3; dir++) {
                // 같은 방향으로 연속 이동 불가
                if(dir == prevDir) continue;
                
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                
                if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    pq.add(new int[]{nx, ny, fuel + board[nx][ny], dir});
                }
            }
        }
    }
    
}

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 단순 BFS처럼만 생각했는데, 이동 방향 제한(같은 방향 연속 불가) 때문에 현재 위치와 누적 연료뿐 아니라, 이전 이동 방향까지 함께 관리해야 한다는 걸 깨달았습니다.

 

• 어떻게 해결했는지

PriorityQueue를 이용하여, 현재까지 누적 연료가 가장 적은 경로부터 탐색하도록 구현했습니다.
이동할 때마다 다음 좌표, 현재까지의 연료 합, 현재 이동 방향을 함께 큐에 넣어 관리했습니다.

 

• 무엇을 새롭게 알았는지

다익스트라 문제에서도 단순히 (x, y)만 고려하는 것이 아니라, 상태(state)를 더 추가해서 풀어야 하는 경우가 있다는 점을 다시 느꼈습니다.
또한, PriorityQueue를 사용하면 최소 비용 경로를 빠르게 찾을 수 있다는 점을 복습할 수 있었습니다.

 

• 내일 학습할 것은 무엇인지

내일은 다익스트라 알고리즘의 다양한 응용 버전, 예를 들어 벽 부수고 이동하기, 최소 비용 구하기 같은 문제를 더 연습할 계획입니다.

---