[이코테] 화성탐사

화성탐사 기계를 탐방하는 로봇을 개발하는 프로그래머.

공간은 N*N이며 [0][0] 부터 [N-1][N-1]까지의 가는 최소한의 비용을 구하시오.

로봇은 상하좌우 한 칸씩 움직일 수 있음.

 

테스트 케이스 : T

테스트 케이스 첫째줄 (공간의 크기): N이후 N개의 줄에 공백으로 각 공간의 크기가 주어짐

 

[입력]

3

3

5 5 4

3 9 1

3 2 7

5

3 7 2 0 1

2 8 0 9 1

1 2 1 8 1

9 8 9 2 0 

3 6 5 1 5 

7

9 8 5 1 1 5 3

4 1 2 1 6 5 3

0 7 6 1 6 8 5 

1 1 7 8 3 2 3

9 4 0 7 6 4 1

5 8 3 2 4 8 3

7 4 8 4 8 3 4  

 

[출력]

20

19

36

 

---

지난 번에 했던 그래프 이론 중에서 어떤 걸 적용해야 하는지 고민이 되었다. 

이진탐색이나 그리디로는 풀 수는 없을 거 같고...

 

5	5	4
3	9	1
3	2	7

가령 이러한 경우에는 5-3-3-2-7 로 총 20이 출력이 된다. 

일단 상하좌우에 갈 수 있으니 상하좌우를 계산할 수 있는 공간 dx, dy를 놓고 시작해야겠다.

int dx[] = {0,1,0,-1}, int dy[] = {-1,0,1,0};

그렇게 하고 노드를 [0][0] 부터 시작하여 탐색하면서 만약 x,y값이 0보다 작거나 공간보다 크다면 continue를 통해 계속해서 탐색해 나간다.

예를 들어 [1][1]을 고려했을 때 9인데 여기서 갈 수 있는 공간은 [1-1][0], [1][1+1], [1-1][1], [1+1][1] 로 총 4개이다. 최소한의 길이를 구하는 것이니까 3,5,1,2가 있을텐데 가장 작은 수를 큐에 넣는 식으로 해서 최종 거리를 구하는 방법으로 풀어보았다. 

 

그리하여 우선순위큐를 사용하여 가장 작은 수를 빼낼 수 있는 다익스트라 알고리즘을 활용하여 문제를 풀고자 하였다.

최소한의 비용을 계산할 수 있는 N*N 공간 dist[][] 하나 더 추가하여 무한(INF)으로 초기화하였고,

Class Node를 추가하여서 x,y좌표와 공간의 비용을 넣을 수 있는 value를 추가하고 이를 우선 순위 큐 속에 넣었다..

 

큐가 빌 때 까지 비용을 계속 계산하여 가장 작은 수라면 dist를 갱신하였고, 가장 작은 수를 dist와 큐에 넣는 식으로 생각하였다.

 

작성한 코드는 아래와 같다. 

 

package codingTest;

import java.util.PriorityQueue;
import java.util.Scanner;

class ExNode{
    int value;
    int x;
    int y;

    public ExNode(int x,int y,int value) {
        this.value = value;
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return this.x;
    }
    public int getY() {
        return this.y;
    }
    public int getValue(){
        return this.value;
    }

}

public class TravelToMars {
    private static int INF = (int) 1e9;
    private static int graph[][];
    private static int T;
    private static int N;

    public static void travelToMars(int graph[][], int dist[][]) {
        // 우선순위 큐 : 가장 작은 값부터 먼저 꺼냄.
        PriorityQueue<ExNode> q = new PriorityQueue<>();

        int len = graph.length;
        int x = 0; int y = 0;
        ExNode exNode;

        exNode = new ExNode(graph[x][y], x, y);
        q.add(exNode);
        dist[x][y] = graph[x][y];


        // 상하좌우 인덱스
        int dx[] = {0,1,0,-1};
        int dy[] = {-1,0,1,0};

        while(!q.isEmpty()) {
            exNode = q.poll();

            int x1 = exNode.getX();
            int y1 = exNode.getY();
            int val = exNode.getValue();


            // 상하좌우 살피기
            for (int i = 0; i < 4; i++) {
                int nx = x1 + dx[i];
                int ny = y1 + dy[i];

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

                int cost = val + graph[nx][ny];

                if(cost<dist[nx][ny]) {
                    dist[nx][ny] = cost;
                    q.add(new ExNode(nx, ny, dist[nx][ny]));
                }
            }

        }
		System.out.println(dist[len-1][len-1]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        N = sc.nextInt();
        graph = new int[N][N];
        int dist[][] = new int[N][N];

        for (int i = 0; i < T; i++) {
            String str[] = sc.nextLine().split(" ");
            for (int j = 0; j < str.length; j++) {
                graph[i][j] = Integer.parseInt(str[i]);
                dist[i][j] = INF;
            }
        }

        travelToMars(graph, dist);

    }
}