(Java/자바) - SW Expert Academy 1249번 : 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

---

• 문제 : 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

저작권 문제로 문제는 링크를 타고 보시길 바랍니다.

 

 

 

---

• 풀이 :

다익스트라 기본형 문제였습니다. 

 

(0,0) 에서 (N-1,N-1) 의 좌표로 이동할 때 가중치의 합이 최소가 되는 최단경로를 찾으면 됩니다.

 

graph에서 가중치를 나타낸 2차원 배열인 board와 x->y의 최단 가중치를 나타낼 distance 배열을 사용합니다.

 

1. 입력받은 가중치를 board에 넣어주고 distance 배열의 모든 값을 MAX_VALUE로 초기화한다. 또한 출발점인 distance[0][0]은 0으로 초기화한다.

 

2. 다익스트라를 구현하기 위해 PriorityQueue 라이브러리를 import해야한다. 이 때, PriorityQueued에 (가중치, x좌표, y좌표)의 객체를 넣기 위해 PriorityQueue의  compareTo를 커스터마이징 해야한다. class Node에서 Node 객체를 구현하고 해당 객체의 정렬 우선순위를 PriorityQueue의 compareTo 함수에 override 해주었다.

 

3.  시작좌표인 [0,0]을 기준으로 상, 하, 좌, 우의  네 방향을 탐색하며 해당 좌표가 갈 수 있는 좌표이고 이미 지나간 경로보다 더 작은 가중치로 이동할 수 있는 경우라면 우선순위 큐에 넣어준다. 이 때, 우선순위 큐는 min_heap으로 동작하므로 항상 거리가 낮은 순서대로 탐색한다.

 

4. 모든 탐색이 끝나면 distance[N-1][N-1]을 출력한다.

 

 

이번에 싸피 8기에 합격하여 자바를 공부하게 되었습니다.

 

자바로 처음 풀어본 알고리즘 문제인데 머릿속에선 금새 구현했지만 자바의 입,출력부터 자료구조, 문법까지 모두가 익숙치 않아 시간이 꽤 오래 걸렸던 문제입니다.

 

꾸준히 자바로 알고리즘을 풀면서 문법과 자료구조에 익숙해지면 좋겠네요

 

 

---

• 소스코드 : 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

class Node implements Comparable<Node>{
	public int w,x,y;
	Node(int w, int x, int y){
		this.w = w;
		this.x = x;
		this.y = y;
	}
	@Override
	public int compareTo(Node node) {
		if (this.w < node.w) {
			return -1;
		} else if (this.w > node.w) {
			return 1;
		}
		return 0;
	}
}

class Solution {
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static int[][] board;
	static int[][] distance;
	static int N;
	
	static void dijkstra() {
		PriorityQueue<Node> pq = new PriorityQueue();
		pq.add(new Node(0,0,0));
		
		while(!pq.isEmpty()) {
			Node curr = pq.poll();
			if (curr.w > distance[curr.x][curr.y]) continue;
			for (int i = 0; i < 4; i++) {
				int ax = curr.x + dx[i];
				int ay = curr.y + dy[i];
				if (0 <= ax && ax < N && 0 <= ay && ay < N) {
					int totalCost = curr.w + board[ax][ay];
					if (totalCost < distance[ax][ay]) {
						distance[ax][ay] = totalCost;
						pq.add(new Node(totalCost, ax, ay));
					}
				}
			}
		}
	}
	
	
	public static void main(String[] args) throws IOException  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			N = Integer.parseInt(br.readLine());
			board = new int[N][N];
			distance = new int[N][N];
			
//			그래프 입력받음
			for (int i = 0; i < N; i++) {
				String[] s = br.readLine().split("");
				for (int j = 0; j < N; j++) {
					board[i][j] = Integer.parseInt(s[j]);					
				}
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					distance[i][j] = Integer.MAX_VALUE;
				}
			}
			distance[0][0] = 0;
			dijkstra();
			System.out.println("#" + (t+1) + " " + distance[N-1][N-1]);
			
		}
	}
}