[백준 Gold 4] 4485 녹색 옷 입은 애가 젤다지? - Java

문제링크 : https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

 

접근 과정 : 

• 링크가 상하좌우로 움직인다.  -> DP불가 and DFS로 하면 힘듬(매 경우마다 visit체크 필요 및 시간초과)
• BFS 와 유사한 방법으로 접근
• 좌표와 해당 좌표까지 잃은 소지금을 PriorityQueue에 집어넣어서 잃은 소지금이 적은 순으로 출력.
• visit[][]를 통해 각 좌표에서의 최소 소지금을 표시.
• PriorityQueue를 통해 하나씩 출력하고, 이로부터 상하좌우를 이동하면서 visit[][] 갱신
• 결국 visit[N-1][N-1]이 최소로 잃은 소지금이다.

1. init() : n과 동굴입력 및 visit[][] 초기화,  만약 n이 0이면 false값 리턴하여 while문 정지
2. findMinRupee() : {0,0,cave[0][0]}를 초기값으로 링크가 길을 진행하면서 최소 소지금을 찾는다.
3. 출력 양식에 맞게 출력

 

소스 코드 및 결과 :

package BOJ;

/* 
    녹색 옷 입은 애가 젤다지?
*/

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

public class BOJ4485 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        new BOJ4485().solution();
    }

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int N;
    int[][] cave;
    int[][] visit;
    int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    void solution() throws NumberFormatException, IOException {

        StringBuilder answer = new StringBuilder();
        int testNumber = 1;

        while (true) {

            if (!init()) {
                break;
            }

            findMinRupee();

            answer.append("Problem ").append(testNumber).append(": ").append(visit[N - 1][N - 1]).append("\n");
            testNumber++;
        }

        System.out.println(answer.toString().trim());
    }

    boolean init() throws NumberFormatException, IOException {

        N = Integer.parseInt(br.readLine());
        if (N == 0) {
            return false;
        }

        int max = N * N * 10;
        cave = new int[N][N];
        visit = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                cave[i][j] = Integer.parseInt(st.nextToken());
                visit[i][j] = max;
            }
        }

        return true;
    }

    int findMinRupee() {

        int rupee = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return a[2] - b[2];
        });
        pq.add(new int[] { 0, 0, cave[0][0] });

        while (!pq.isEmpty()) {
            int[] now = pq.poll();

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + move[i][0];
                int ny = now[1] + move[i][1];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                    continue;
                }

                if (visit[nx][ny] > cave[nx][ny] + now[2]) {
                    visit[nx][ny] = cave[nx][ny] + now[2];
                    pq.add(new int[] { nx, ny, visit[nx][ny] });

                }
            }
        }

        return rupee;
    }

}

 

P.S 

이 문제가 다익스트라 유형에 포함되는지 잘 모르겠다...