백준 4485 자바 - 녹색 옷 입은 애가 젤다지? (BOJ 4485 JAVA)

문제 : boj4485

 

 

1.

  젤다가 활강하는 장면! 야숨2가 나오면 알고리즘을 당분간 못(안)풀 수 있으니 알고리즘을 미리 풀고 키핑해둬야겠다ㅋㅋㅋ

 

 

2. 

  만약 이런식의 문제에서 이동 가능한게 좌측과 아래쪽 뿐이었다면 DP로도 풀 수 있다. 하지만 이 문제와 같이 4방향으로 이동이 가능하다면, DP로 풀어보려면 결국 모든 경우를 다 봐야해서 시간초과가 나게 될 것이다. O((N^2)^2)

 

  한가지 떠올릴만한 점은 결국 배열도 그래프라는 것이다. 예제 입력의 아래와 같은 부분을 그래프 형태로 그려보면 다음과 같다.

3
5 5 4
3 9 1
3 2 7

 

  결국 이 문제는 가장 적게 잃으면서 진행해야 하므로, 그냥 그래프에서 start부터 goal 까지의 최단거리를 찾는 것과 동일하다! 그리고 가중치가 모두 양수이면서, 서로 가중치가 다르므로 다익스트라(dijkstra)를 쓰면 될 것임을 알 수 있다. 평소 다익스트라를 그래프 형태에서만 해봤다면 배열형태라 좀 어색할수도 있겠으나 방식은 동일하다.

 

 

3.

  추가로 내 경우엔 2차원 배열로 안보고 그냥 1차원 배열로 보고 풀어봤다. 아래와 같이 row단위로 옆으로 쭉 펼쳐서 1차원 배열로 만든 형태이다.

    2차원 배열 그대로 하든지 1차원으로 바꿔서 하든지 차이는 없다. 그냥 해보고 싶었다. 2차원 배열일 때 배열의 인접한 부분이 결국 간선이 존재하는 것이고, 가중치는 예를들어 '3'에서 '9'로 간다면 해당 간선의 가중치는 9인 셈이다. 이런식으로 다익스트라를 돌리면 된다. 1차원으로 풀어도 결국 인접한 위치를 찾아내는 수식만 바뀔 뿐 동일한 연산이다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.PriorityQueue;

class Pos implements Comparable<Pos> {
    int num, dist;
    public Pos(int num, int dist) {
        this.num = num;
        this.dist = dist;
    }

    @Override
    public int compareTo(Pos o) {
        return this.dist - o.dist;
    }
}

public class Main extends FastInput {
    private static final int INF = 125*125*9+1;

    private int getNumOfAdjacent(int n, int curNum, int dir) {
        switch (dir) {
            case 0 : if (curNum-n >= 0)     return curNum-n; break;
            case 1 : if (curNum+n < n*n)      return curNum+n; break;
            case 2 : if (curNum%n!=0)       return curNum-1; break;
            case 3 : if (curNum%n!=n-1)     return curNum+1; break;
        }
        return -1;
    }

    private int getAnswer(int n, int[] arr) {
        int[] dist = new int[n*n];
        Arrays.fill(dist, INF);

        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.add(new Pos(0, arr[0]));
        dist[0] = arr[0];
        while (!pq.isEmpty()) {
            Pos cur = pq.poll();
            if (cur.dist > dist[cur.num]) continue;
            for (int dir = 0; dir < 4; dir++) {
                int next = getNumOfAdjacent(n, cur.num, dir);
                if (next == -1 || cur.dist + arr[next] >= dist[next]) continue;
                dist[next] = cur.dist + arr[next];
                pq.add(new Pos(next, dist[next]));
            }
        }

        return dist[n*n-1];
    }

    private void solution() throws Exception {
        int tc = 1;
        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = nextInt();
            if (n == 0) break;

            sb.append("Problem ").append(tc++).append(':').append(' ');
            int[] arr = new int[n*n];
            for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) arr[n*i+j] = nextInt();
            sb.append(getAnswer(n, arr)).append('\n');
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}