[백준] 17484번. 진우의 달 여행 (Small)(JAVA)

문제

https://www.acmicpc.net/problem/17484

---

풀이(15분)

import java.io.*;
import java.util.*;

public class Main {

    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][m]; // 지도
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Queue<Node> queue = new LinkedList<>(); // bfs를 진행할 큐

        for(int i = 0; i < m; i++){
            queue.add(new Node(0, i, 4, 0)); // 최초 시작점
        }

        int min = Integer.MAX_VALUE;
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            if(cur.row == n-1){
                min = Math.min(min, cur.total + arr[cur.row][cur.col]);
                continue;
            }

            // 이전에 좌하단으로 내려온 것이 아니라면
            if(cur.direction != 0){
                if(isInBounds(cur.row + 1, cur.col - 1)){
                    queue.add(new Node(cur.row + 1, cur.col - 1, 0, cur.total + arr[cur.row][cur.col]));
                }
            }

            // 이전에 하단으로 내려온 것이 아니라면
            if(cur.direction != 1){
                if(isInBounds(cur.row + 1, cur.col)){
                    queue.add(new Node(cur.row + 1, cur.col, 1, cur.total + arr[cur.row][cur.col]));
                }
            }

            // 이전에 우하단으로 내려온 것이 아니라면
            if(cur.direction != 2){
                if(isInBounds(cur.row + 1, cur.col + 1)){
                    queue.add(new Node(cur.row + 1, cur.col + 1, 2, cur.total + arr[cur.row][cur.col]));
                }
            }
        }

        System.out.println(min);
    }

    static boolean isInBounds(int row, int col){
        return row >= 0 && row < n && col >= 0 && col < m;
    }

    static class Node{
        int row, col, direction, total;
        // direction 0 : 좌하단, 1 : 하단, 2 : 우하단, 4 : 상관없음
        public Node(int row, int col, int direction, int total){
            this.row = row;
            this.col = col;
            this.direction = direction;
            this.total = total;
        }
    }

}

---

문제 풀이 전략

 

처음엔 dp를 통해 문제를 해결해 볼까 하였지만 이전의 전 단계까지 고려해야 한다는 부분에서 bfs가 더욱 편리할 것이라고 생각했다.

 

Node에 좌표와 방향, 총 값을 넣고 bfs를 진행하며 이 전 이동 방향을 제외하고 추가해 주는 움직임을 취하였다.