[JAVA] SWEA_보급로

 

최근에 백준에서 동일한 문제를 푼 기억이 있어서 금방 풀었던 문제이다.

 

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

 

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

 

 

| 문제 해결방법

 

다익스트라 + 우선순위 큐

 

★다익스트라 알고리즘과 우선순위 큐(Priority Queue)를 함께 사용하면 효율이 극대화된다.

 

[JAVA] 해설 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
 
 
class node implements Comparable<node>{
    int r, c, cost;
 
    public node(int r, int c, int cost) {
        super();
        this.r = r;
        this.c = c;
        this.cost = cost;
    }
    // 비용으로 정렬하기
    @Override
    public int compareTo(node o) {  
        return this.cost - o.cost;
    }
 
}
public class Solution {
 
     
    static int N, INF;
    static int[][] arr, dijk;
    static boolean[][] visited;
    static int[] dr = {-1,0,1,0}; // 상, 우, 하, 좌
    static int[] dc = {0,1,0,-1};
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
        INF = 100000;
         
         
        for(int tc = 1; tc <= T ;tc++) {
             
             
            N = Integer.parseInt(br.readLine());
            // 입력받은 정보를 저장하는 배열
            arr = new int[N][N];
            // 최소 복구 시간을 저장하는 배열
            dijk = new int[N][N];
            visited = new boolean[N][N];
            for(int i=0;i<N;i++) {
                char[] c = br.readLine().toCharArray();
                for(int j=0;j<N;j++) {
                    // MIN값을 저장하기 위해 INF값으로 초기화
                    dijk[i][j] = INF;
                    arr[i][j] = c[j] -'0';
                }
            }
 
            sb.append("#"+tc+" ").append(bfs()).append("\n");
             
        }
        System.out.println(sb.toString());
         
    }
    private static int bfs() {
        // 우선순위 큐를 사용해 최소 비용의 지점을 먼저 선택할 수 있도록 한다.
        PriorityQueue<node> q = new PriorityQueue<>();
        q.offer(new node(0,0,0));
        // 시작점 0,0
        visited[0][0] =true;
         
        while(!q.isEmpty()) {
            node n = q.poll();
             
            for(int i=0;i<4;i++) {
                int nr = n.r + dr[i];
                int nc = n.c + dc[i];
                 
                // 범위를 벗어났거나, 방문했던 곳이라면 패스
                if(!isIn(nr,nc) || visited[nr][nc])
                    continue;
                 
                // 최소 비용 저장하기
                if(n.cost+arr[nr][nc] < dijk[nr][nc]) {
                    dijk[nr][nc] = n.cost+arr[nr][nc];
                    q.offer(new node(nr,nc,dijk[nr][nc]));
                    visited[nr][nc] =true;
                }
                 
            }
        }
         
        // 끝나는 지점 N-1, N-1
        return dijk[N-1][N-1];
    }
 
    private static boolean isIn(int r, int c) {
        return r>=0 && r<N && c>= 0 && c<N;
    }
}

 

 

[제출] 메모리 및 시간