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

https://www.acmicpc.net/problem/4485

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

대표적인 다익스트라 알고리즘을 사용하는 문제이다.

행렬의 출발지점으로 부터 시작해서 마지막 지점까지 최대한 적은 비용으로 자취를 구하여 해당 총 비용을 구해주면 된다.

 

아래와 같은 행렬이 있고 링크가 (0,0) 지점 부터  (2,2) 지점까지 상하좌우로 움직이는데 가장 적은 비용을 지불하면서

도착하는 경로를 구해주면 된다.

여러가지 경로 중 아래의 경로가 존재할 것이다.

 

링크가 위와 같은 경로를 통해 마지막 도착점에 도착한다면 총 비용은 26이 들게된다.

또한, 아래와 같은 경로도 존재할 것이다.

 

위와 같은 경로를 통해서 링크가 출발지점으로 부터 출발해 도착지점에 도착하게 된다면

비용은 총 20이 들것이다.

 

그럼 총 비용 26이 발생하는 경로보다는 총 비용 20이 발생하는 경로가 더 최 최소비용을 소비하는 것이므로

아래의 경로를 통해서 가는 방법을 택하면 된다.

 

해당 문제를 푸는 방법론을 요약하면 아래와 같다.

 

1. 다익스트라 알고리즘을 사용하여 최단경로를 구해준다.

2. 링크가 서있는 시점에서는 상하좌우 를 움직일 수 있도록 도와주는 방향 배열을 생성하여 사용하게끔 한다.

3. 0을 입력받으면 프로그램은 종료된다.

 

 

 

1. JAVA 풀이

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

public class Main
{   
    static int N;
    static int INF = Integer.MAX_VALUE;
    static int CASE = 1;
    static int[][] vertex;
    static int[][] dist;
    static int[] dr = {0,0,-1,1};
    static int[] dc = {1,-1,0,0};
    
    static class Node {
        int r,c,dist;
        
        public Node(int r, int c, int dist) {
            this.r = r;
            this.c = c;
            this.dist = dist;
        }
    }
    
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
	    while(true) {
	        N = Integer.parseInt(br.readLine());
	        
	        if (N == 0) break;
	        
	        vertex = new int[N][N];
	        dist = new int[N][N];
	        
	        for (int i = 0; i < N; i++) {
	            String[] inputs = br.readLine().split(" ");
	            for (int j = 0; j < N; j++) {
	                vertex[i][j] = Integer.parseInt(inputs[j]);
	            }
	        }
	        
	        initial();
	        dijkstra();
	        answer();
	    }
	    br.close();
	}
	
	static void dijkstra() {
	    PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
			@Override
			public int compare(Node n1, Node n2) {
				
				if (n1.dist > n2.dist) return -1;
				else if (n2.dist > n1.dist) return 1;
				else return 0;
			}
		});
		
		dist[0][0] = vertex[0][0];
		pq.offer(new Node(0,0,-dist[0][0]));
		
		while(!pq.isEmpty()) {
		    Node nd = pq.poll();
		    
		    int curR = nd.r;
		    int curC = nd.c;
		    int curDist = -nd.dist;
		    
		    for (int i = 0; i < 4; i++) {
		        int newR = curR + dr[i];
		        int newC = curC + dc[i];
		        
		        if (newR >= 0 && newC >= 0 && newR < N && newC < N) {
		            if (dist[newR][newC] > curDist + vertex[newR][newC]) {
		                dist[newR][newC] = curDist + vertex[newR][newC];
		                pq.offer(new Node(newR,newC, -dist[newR][newC]));
		            }
		        }
		    }
		}//while
	}
	
	static void answer() {
	    System.out.printf("Problem %d: %d\n",CASE++, dist[N-1][N-1]);
	}
	
	static void initial() {
	    for (int i = 0; i < N*N; i++) {
	        dist[i/N][i%N] = INF;
	    }
	}
}

 

 

 

2. C++ 풀이

#include <iostream>
#include <queue>
#include <vector>
#include <limits.h>

using namespace std;

int INF = INT_MAX;
int vertex[126][126];
int distances[126][126];
int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,-1,1};
int COUNT = 1;
int N;

void clean() {
    for (int i = 0; i < N*N; i++) {
        distances[i/N][i%N] = INF;
        vertex[i/N][i%N] = 0;
    }
}

void dijkstra() {
    priority_queue < pair< int,pair<int,int> > > pq;
    distances[0][0] = vertex[0][0];
    pq.push(make_pair(-vertex[0][0],make_pair(0,0)));

    while(!pq.empty()) {
        int cur_d = -pq.top().first;
        int cur_r = pq.top().second.first;
        int cur_c = pq.top().second.second;
        
        pq.pop();

        for (int i = 0; i < 4; i++) {
            int next_r = dr[i] + cur_r;
            int next_c = dc[i] + cur_c;

            if (next_r >= 0 && next_c >= 0 && next_r < N && next_c < N) {
                if (distances[next_r][next_c] > cur_d + vertex[next_r][next_c]) {
                    distances[next_r][next_c] = cur_d + vertex[next_r][next_c];
                    pq.push(make_pair(-distances[next_r][next_c],make_pair(next_r,next_c)));
                }
            }

        }
    }//while
}

int main()
{

    while(1) {
        cin >> N;

        if (N == 0) break;
        
        clean();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> vertex[i][j];
            }
        }

        dijkstra();

        cout << "Problem " << COUNT++ << ": " << distances[N-1][N-1] << "\n";
    }

}