[알고리즘] 백준 4485 녹색 옷 입은 애가 젤다지? -다익스트라 + BFS, 최단경로 - 자바 코틀린

 

 

www.acmicpc.net/problem/4485

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

 

 

백준 다익스트라 유형을 풀어봤습니다. ㅎㅎ 

어렸을때 닌텐도로 젤다의 전설 게임을 한 경험이 있는데 문제를 읽으며 젤다가 그 주인공이 아니라 공주였다는 사실을 저도 처음알았네요 ;; 

 

문제에 대해 간략히 쉽게 설명하면 N*N 맵이 있고 (0,0) 에서 (N,N) 까지 가는 최소비용을 구하는 문제였습니다.

 

이전에 ArrayList 배열 즉 인접리스트를 사용하여 풀었던 다익스트라 문제와 다르게 BFS 4방향 이동을 조합한 풀이로 좋은 공부가 되었습니다.  

 

 

풀이는 다음과 같습니다.

 

[Java]

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

public class Main {
    private static int N;
    private static int[][] map;
    private static int[][] distances;
    private static int INF = Integer.MAX_VALUE;
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCnt = 0;
        while (true) {
            N = sc.nextInt();
            if(N==0) return;
            map = new int[N][N];
            distances = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = sc.nextInt();
                    distances[i][j] = INF;
                }
            }
            System.out.println("Problem " + (++testCnt) + ": " + bfs());
        }
    }

    static int bfs() {
        PriorityQueue<Point> queue = new PriorityQueue<>();
        queue.add(new Point(0, 0, map[0][0]));
        distances[0][0] = map[0][0];
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int r = point.r;
            int c = point.c;
            for (int i = 0; i < 4; i++) {
                int r2 = r + dr[i];
                int c2 = c + dc[i];
                if (r2 >= 0 && c2 >= 0 && r2 < N && c2 < N && (distances[r2][c2] > distances[r][c] + map[r2][c2])) { // 해당 지점까지의 최소거리라면 갱신
                    distances[r2][c2] = distances[r][c] + map[r2][c2];
                    queue.add(new Point(r2, c2, distances[r2][c2]));
                }
            }
        }
        return distances[N - 1][N - 1];
    }

    static class Point implements Comparable<Point>{
        int r;
        int c;
        int cost;

        public Point(int r, int c, int cost) {
            this.r = r;
            this.c = c;
            this.cost = cost;
        }

        @Override
        public int compareTo(Point o) {
            return cost - o.cost;
        }
    }
}

 

 

[Kotlin]

import java.util.*

private var N = 0
private lateinit var map: Array<IntArray>
private lateinit var distances: Array<IntArray>
private val dr = intArrayOf(-1, 0, 1, 0)
private val dc = intArrayOf(0, -1, 0, 1)


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    var testCnt = 0
    while (true) {
        N = sc.nextInt()
        if (N == 0) return
        map = Array(N) { IntArray(N) }
        distances = Array(N) { IntArray(N) }
        for (i in 0 until N) {
            for (j in 0 until N) {
                map[i][j] = sc.nextInt()
                val INF = Int.MAX_VALUE
                distances[i][j] = INF
            }
        }
        println("Problem " + ++testCnt + ": " + bfs())
    }
}

fun bfs(): Int {
    val queue = PriorityQueue<Point>()
    queue.add(Point(0, 0, map[0][0]))
    distances[0][0] = map[0][0]
    while (!queue.isEmpty()) {
        val point = queue.poll()
        val r = point.r
        val c = point.c
        for (i in 0..3) {
            val r2 = r + dr[i]
            val c2 = c + dc[i]
            if (r2 >= 0 && c2 >= 0 && r2 < N && c2 < N && distances[r2][c2] > distances[r][c] + map[r2][c2]) { // 해당 지점까지의 최소거리라면 갱신
                distances[r2][c2] = distances[r][c] + map[r2][c2]
                queue.add(Point(r2, c2, distances[r2][c2]))
            }
        }
    }
    return distances[N - 1][N - 1]
}

internal class Point(var r: Int, var c: Int, var cost: Int) : Comparable<Point?> {

    override fun compareTo(other: Point?): Int {
        return cost - other!!.cost
    }

}

 

 

 

댓글과 공감은 큰 힘이 됩니다.  감사합니다. !!