백준 - 4485 녹색 옷 입은 애가 젤다지?

---

풀이 방법

오랜만에 도전한 골드 문제!!

처음에 생각없이 BFS 로 코드를 짰는데 메모리 초과가 발생해서 방향을 다시 잡고 코드를 치기 시작했다.

 

이 문제의 핵심 포인트는 녹색옷을 입을 애가 젤다라는 점!! 이 아니고ㅋㅋㅋㅋ

2차원 배열로 입력받는다고 하더라도 결국 n-1, n-1 좌표에 도착하는 최소값을 구하는 문제라는 점이다.

BFS 나 DFS 로 푸는것이 아니라 다익스트라 알고리즘을 사용해야한다. 다만 우리는 그래프 형식이 아니고 배열로 입력받기 때문에 어떻게 좌표(노드)에서 좌표(노드) 로 넘어갈 수 있는지 고민해야한다. 나는 이 부분을 DFS, BFS 에서 사용하던 dx, dy 배열을 사용해서 풀이를 하였다.

 

즉, dx, dy 를 통해 계산된 nx, ny 좌표가 배열의 범위 안에 존재하면 이전 좌표에서 다음 좌표로 이동할 수 있다고 가정하고 다익스트라 알고리즘 계산을 하고, 아닌 경우 움직일 수 없다고 판단 queue 를 종료하는 방식으로 만들었다.

 

다소 어렵기는 했지만, 다익스트라와 dx, dy 를 잘 이용한다면 크게 어려움없는 문제라고 생각한다. 오히려 출력 형식 때문에 3번이나 틀렸다ㅠㅠ

 

자세한 내용은 주석 참고!!

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// https://www.acmicpc.net/problem/4485
public class Quiz_4485 {

    static int[][] maze;
    static int[][] dijkstra;

    // 2차원 배열에서 움직이기 위한 배열 dx, dy
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n;
    static Queue<Rupee> q;

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

        // 몇번째 problem 인지 알기 위해서 cnt 변수 선언
        int cnt = 1;
        // n == 0 일때까지 받아야 하기 때문에 while 문 시작
        while (true) {

            n = Integer.parseInt(br.readLine());
            if (n == 0) {
                break;
            }

            // maze 는 입력받는 2차원 배열
            // dijkstra 는 다이스트라 알고리즘을 위한 배열 => 각 노드 방문시 최종 cost 를 저장하기 위한 배열
            maze = new int[n][n];
            dijkstra = new int[n][n];

            // 큐는 PriorityQueue 로 만들고, cost 를 기준으로 오름차순으로 튀어나오도록 설정
            q = new PriorityQueue<>((o1, o2) -> {
                return o1.cost - o2.cost;
            });

            // maze 를 입력받고, dijkstra 에는 최대값을 저장한다.
            for(int i=0; i<n; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());

                for(int j=0; j<n; j++){
                    maze[i][j] = Integer.parseInt(st.nextToken());
                    dijkstra[i][j] = Integer.MAX_VALUE;
                }
            }

            // queue 에 시작점을 넣고 시작!!
            q.offer(new Rupee(0, 0, maze[0][0]));
            System.out.println(findLose(cnt));
            cnt++;
        }

    }

    static String findLose(int cnt){
        while (!q.isEmpty()) {
            Rupee r = q.poll();
            int x = r.x;
            int y = r.y;
            int cost = r.cost;

            // 2차원 배열로 입력받고, 움직이는만큼 결국 풀이의 기본을 DFS, BFS 문제들처럼 생각한다.
            // 즉 노드끼리 연결되서 갈 수 있는 곳은 결국 BFS 나 DFS 문제에서 움직이는 것처럼
            // dx, dy 를 이용한다.
            for(int i=0; i<4; i++){
                int nx = x+dx[i];
                int ny = y+dy[i];

                // nx, ny 의 범위 지정
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                    continue;
                }

                // ncost 는 위치의 cost 와 앞으로 움직일 지점의 cost
                int ncost = cost+maze[nx][ny];

                // 현재 위치의 cost 가 dijkstra[x][y] 의 값보다 크다면 continue;
                // 왜냐하면 이미 더 크기 때문에 이 이상 계산할 필요X
                if (cost > dijkstra[x][y]) {
                    continue;
                }

                // 만약 n-1, n-1 좌표에 도착한다면 끝!
                if (nx == n - 1 && ny == n-1) {
                    return "Problem "+cnt+": "+ncost;
                }else if(dijkstra[nx][ny] > ncost){
                    // 만약 dijkstra[nx][ny] 의 cost 값보다 ncost 값이 작다면
                    // dijkstra 좌표의 값을 변경 후 queue 에 넣기
                    dijkstra[nx][ny] = ncost;
                    q.offer(new Rupee(nx, ny, ncost));
                }
            }

        }

        return null;
    }
}

class Rupee{
    int x;
    int y;
    int cost;

    Rupee(int x, int y, int cost) {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }
}