1249. [S/W 문제해결 응용] 4일차 - 보급로 java

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=JAVA&select-1=4&pageSize=10&pageIndex=2

SW Expert Academy

 

 

입력 n*n크기의 배열이 있고,

S -> G 에 도달할때의 최소비용을 출력하는 문제이다. 

DFS로 풀려고했으나 완전탐색으로는 시간초과되어 다익스트라 알고리즘을 사용했다.

정점과 간선정보가 있을때만 다익스트라 알고리즘을 사용했었는데 배열에서도 헷갈리긴 했지만

풀고보니 큰 차이가 없었다.

차이가 있다면 정점과 간선일때는 list자료형에 인접리스트 정보를 저장 후 접근하는 방식이고 배열은 이동가능한 방향으로 접근하는 차이.

 

풀이:

1.

n*n 크기의 배열 arr, dis 을 선언한다. arr은 단순하게 주어진 입력을 받고 최소거리를 찾는데 사용될 배열이고

dis배열은 예를 들어, dis[1][1] : 시작지점(arr[0][0])에서 출발해 arr[1][1]까지 가는데 소요되는 최소비용.

dis배열은 출발지점 S를 제외하고 각 배열의 데이터를 Integer.MAX_VALUE로 한다.

(각 최소거리를 구하기 위해서 우선 높은값으로 초기화 함)

 

2.

arr배열은 2차원 배열이기 때문에 좌표 y,x 와 비용 cost를 저장하는 Edge 클래스 생성.

Edge클래스를 담는 우선순위 큐(pq) 생성. 

(우선순위 큐인 pq는 poll() 작업 수행할때마다 가장 작은 비용인 Edge를 꺼냄)

pq에 시작지점과 비용 (0,0,0)을 넣어주고 다익스트라 

알고리즘으로 최소거리를 구함. 

 

3.

다익스트라 알고리즘의 핵심은 시작지점에서 이동할때마다 누적된 값과 최소거리를 저장하는 dis배열에서 

작은값을 dis배열에 저장한 뒤 도착지점 G의 거리를 정답을 출력하는 answer 변수에 담아 출력.

 

 전체코드

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

class Solution
{
    static class Edge implements Comparable<Edge>{
        public int y;
        public int x;
        public int cost;
        Edge(int y, int x, int cost){
            this.y = y;
            this.x = x;
            this.cost = cost;
        }
        @Override
        public int compareTo(Edge e) {
            return this.cost- e.cost;
        }
    }
    static int n;
    static int[][] arr;
    static int[][] dis;
    static int[] dy={-1,0,1,0};
    static int[] dx={0,1,0,-1};
    static int answer;
    public void dijkstra(){
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(0,0, 0));
        while (!pq.isEmpty()){
            Edge tmp = pq.poll();
            for(int i=0; i< 4; i++) {
                int ny = tmp.y + dy[i];
                int nx = tmp.x + dx[i];
                if(ny < 0 || ny >=n || nx<0 || nx>=n) continue;
                // tmp.cost + arr[ny][nx] : 이동할때마다 비용을 누적
                if(dis[ny][nx] > tmp.cost + arr[ny][nx]) {
                    dis[ny][nx] = tmp.cost + arr[ny][nx];
                    pq.add(new Edge(ny,nx,tmp.cost + arr[ny][nx]));
                }
            }
        }
    }
	public static void main(String args[]) throws Exception
	{
	
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int tc = 1; tc <= T; tc++)
		{
			Solution s = new Solution();
			answer=Integer.MAX_VALUE;
			//input
			n = sc.nextInt();
			arr = new int[n][n];
			dis = new int[n][n]; // 최소거리 저장 배열
			for(int i=0;i<n;i++){
				String str = sc.next();
				for(int j=0;j<n;j++){
					arr[i][j] = Integer.parseInt(str.charAt(j)+"");
				}
			}
			for(int i=0;i<n;i++) Arrays.fill(dis[i],Integer.MAX_VALUE);
			dis[0][0]=0;
			s.dijkstra();
			answer = dis[n-1][n-1];
			System.out.println("#"+tc+" "+answer);

		}
	}
}