[SWEA] JAVA - 1249. 보급로

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

SW Expert Academy

생각

(0,0) -> (N-1, N-1)로 갈때 최소 비용으로 가는 비용을 찾는 문제입니다. 최소 비용을 찾는 문제이므로 경로가 단순하게 좌 -> 우 or 위 -> 아래 방향이 아니라 돌아서 갈 수 있기 때문에 BFS + 우선순위 큐를 사용하여 최소 비용을 가지는 지점을 가장 먼저 탐색하도록 했습니다.

 

1. 우선순위 큐를 생성하고 시작 위치를 넣어줍니다.

2. 큐가 빌때까지 3~5번 작업을 반복합니다.

3. 우선순위 큐에서 poll()을 한뒤 도착지점이라면 while문을 탈출하도록 합니다. 

4. 아직 방문하지 않았으면 방문 체크를 해줍니다. -> 우선순위 큐를 사용했기 때문에 큐에 담겨 있지만 비용이 커서 사용을 안 할수도 있습니다. 따라서 일반적인 BFS는 방문체크를 큐에 add 할때 같이 방문체크를 해주지만 우선순위 큐이기 때문에 큐에서 뺄 때 방문 체크를 해줘야 합니다!

5. 갈 수 있는 지점을 탐색한뒤 아직 방문하지 않았다면 큐에 넣어줍니다.

 

Java Code

package com.java.algorithm;

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

public class SWEA_1249_보급로 {
	static int N;
	static int[][] map;
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,1,-1};
	
	static class Pos implements Comparable<Pos>{
		int y,x,cost;
		
		public Pos(int y, int x, int cost) {
			super();
			this.y = y;
			this.x = x;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Pos o) {
			return Integer.compare(this.cost, o.cost);
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				String[] temp = br.readLine().split("");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(temp[j]);
				}
			}
			sb.append("#").append(t).append(" ").append(solve()).append("\n");
		}
		System.out.println(sb);

	}
	private static int solve() {
		boolean[][] visited = new boolean[N][N];
		int ans = 0;
		PriorityQueue<Pos> q = new PriorityQueue<Pos>();
		q.add(new Pos(0,0,0));
		
go:		while(!q.isEmpty()) {
			int size = q.size();
			while(size-- > 0) {
				Pos now = q.poll();
				
				if(now.y == N-1 && now.x == N-1) {
					ans = now.cost;
					break go;
				}
				
				if(visited[now.y][now.x]) continue;
				visited[now.y][now.x] = true;
				
				for (int d = 0; d < 4; d++) {
					int ny = now.y + dy[d];
					int nx = now.x + dx[d];
					if(ny >= N || ny < 0 || nx >= N || nx < 0) continue;
					if(!visited[ny][nx]) {
						q.add(new Pos(ny, nx, now.cost + map[ny][nx]));
					}
				}

			}
		}
		return ans;
	}

}