[BOJ 4485] 녹색 옷 입은 애가 젤다지? (Java)

문제

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

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

 

풀이

오랜만에 다익스트라 알고리즘 문제를 풀어 보았다. 

나는 아래와 같이 풀었다. 

 

1. 간선에 대한 정보가 명시적으로 주어지지 않기 때문에 직접 만든다.

배열을 순회하면서 상하좌우를 체크하여 접근 가능한 좌표라면 현재 배열 좌표에 인접한 좌표라고 볼 수 있다. 

이때 인접한 좌표의 배열 값이 해당 좌표를 가기 위한 가중치 값이 된다. 

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(int[] d : dir){
                    int nx = i + d[0];
                    int ny = j + d[1];
                    if(isValid(nx, ny, N)){
                        adjs[i][j].add(new Edge(nx, ny, map[nx][ny]));
                    }
                }
            }
        }

adjs[i][j].add(new Edge(nx, ny, map[nx][ny]));

adjs[i][j] 는 (i, j) 좌표와 인접한 좌표 정보들을 담는다.

Edge는 인접 좌표와 해당 좌표로 가기 위한 가중치 정보를 담는다.

 

2. 좌표의 수만큼 최소 가중치를 저장할 배열을 만들어서 INF 값을 넣어둔다.

        // 최단 거리를 담을 배열 생성
        int[][] dist = new int[N][N];
        for(int i = 0; i < N; i++){
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

 

3. 우선 순위 큐를 생성한 후 시작 좌표 정보를 넣어준다. 

Info객체는 현재 좌표와 현재 좌표까지의 가중치의 합 정보를 가진다.

pq의 정렬은 Info 객체에 Comparable로 구현했으며, 가중치 적은 순으로 정렬된다. (가중치 기준 최소 힙)

계산 횟수 줄이기 위함

        // 시작 노드 정보 넣어주기.
        PriorityQueue<Info> pq = new PriorityQueue<Info>();
        pq.offer(new Info(0, 0, map[0][0]));

 

4. 인접 좌표를 탐색해 나가며 최소 가중치 배열의 값을 갱신해 나간다. 

이 때 현재 좌표까지의 가중치 + 인접 좌표의 가중치가 인접 좌표 최소 가중치 배열에 저장된 값보다 작을 경우 

dist 배열의 값을 갱신해 준다. 반대 케이스의 경우, 더 이상 탐색할 필요가 없기 때문에 pq에 넣지 않는다.

        while(!pq.isEmpty()){
            Info info = pq.poll();
            if(info.dist > dist[info.x][info.y]) continue;
            // 현재 노드의 인접 노드를 순회한다.
            for(Edge edge : adjs[info.x][info.y]){
                // (시작노드부터 현재노드까지의 가중치  + 인접노드로 가기 위한 가중치)가 
                // 인접노드의 최단 가중치 배열에 저장된 값보다 작을 경우
                // 최단 가중치 배열에 해당 값을 갱신해 준다.
                // 그리고 그 인접노드 정보와 인접노드까지의 가중치를 pq에 넣는다.
                if(info.dist + edge.weight < dist[edge.toX][edge.toY]){
                    dist[edge.toX][edge.toY] = info.dist + edge.weight;
                    pq.offer(new Info(edge.toX, edge.toY, info.dist + edge.weight));
                }
            }
        }

 

5. dist[N-1][N-1] 값 리턴

 return dist[N-1][N-1];

 

소스코드

package dijkstra;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ3385 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int idx = 1;
        while(true){
            int N = Integer.parseInt(br.readLine());
            if(N == 0) break;
            int[][] map = new int[N][N];
            StringTokenizer st = null;
            for(int i = 0; i < N; i++){
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < N; j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            bw.write("Problem " + idx + ": "+ solution(N, map) + "\n");
            idx++;
        }
        bw.flush();

    }

    public static class Edge {
        int toX;
        int toY;
        int weight;

        public Edge(int toX, int toY, int weight){
            this.toX = toX;
            this.toY = toY;
            this.weight = weight;
        }
    }

    public static class Info implements Comparable<Info>{
        int x;
        int y;
        int dist;

        public Info(int x, int y, int dist){
            this.x = x;
            this.y = y;
            this.dist = dist;
        }

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

    // 현 노드에서 접근 가능한 좌표를 구할때 사용할 정보 (상하좌우)
    public static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static int solution(int N, int[][] map){
        // 최단 거리를 담을 배열 생성
        int[][] dist = new int[N][N];
        for(int i = 0; i < N; i++){
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        // 각 노드의 인접 노드 리스트 생성
        ArrayList<Edge>[][] adjs = new ArrayList[N][N];
        for(int i = 0 ;i< N; i++){
            for(int j =0; j < N; j++){
                adjs[i][j] = new ArrayList<Edge>();
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(int[] d : dir){
                    int nx = i + d[0];
                    int ny = j + d[1];
                    if(isValid(nx, ny, N)){
                        adjs[i][j].add(new Edge(nx, ny, map[nx][ny]));
                    }
                }
            }
        }

        // 시작 노드 정보 넣어주기.
        PriorityQueue<Info> pq = new PriorityQueue<Info>();
        pq.offer(new Info(0, 0, map[0][0]));

        while(!pq.isEmpty()){
            Info info = pq.poll();
            if(info.dist > dist[info.x][info.y]) continue;
            // 현재 노드의 인접 노드를 순회한다.
            for(Edge edge : adjs[info.x][info.y]){
                // (시작노드부터 현재노드까지의 가중치  + 인접노드로 가기 위한 가중치)가 인접노드의 최단 가중치 배열에 저장된 값보다 작을 경우
                // 최단 가중치 배열에 해당 값을 갱신해 준다.
                // 그리고 그 인접노드 정보와 인접노드까지의 가중치를 pq에 넣는다.
                if(info.dist + edge.weight < dist[edge.toX][edge.toY]){
                    dist[edge.toX][edge.toY] = info.dist + edge.weight;
                    pq.offer(new Info(edge.toX, edge.toY, info.dist + edge.weight));
                }
            }
        }

        return dist[N-1][N-1];
    }

    public static boolean isValid(int x, int y, int N){
        if(x < 0 || y < 0 || x >= N || y >= N) return false;
        return true;
    }
}