[Java] SWEA1249_보급로

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

SW Expert Academy

 

[문제]

 

2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다.
전투가 진행중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다.
그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다.
전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다.
공병대는 출발지(S) 에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다.
도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.
출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오.
깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.

[입력]

 

1             //테스트케이스 개수
4             //정사각형 배열 크기
0100        //배열정보
1110
1011
1010

 

[출력]

 

#1 2

 

[풀이]

 

백준 젤다문제와 매우 흡사하여 빠른시간내에 풀 수 있었다.

(젤다문제는 하단 링크 참조)

가중치에 대하여 최소누적합을 구하는 문제이므로 다익스트라를 사용하였다.

정렬의 편의성을 위해 PriorityQueue를 사용하였다.

 

https://java-is-happy-things.tistory.com/35

PriorityQueue(우선순위 큐)

 

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

public class SWEA1249_보급로 {
	
	static int[][] map,ans;
	static boolean[][] visited;
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		for(int t=1; t<=tc; t++) {
			N = Integer.parseInt(br.readLine());
			map=new int[N][N];
			ans=new int[N][N];
			visited=new boolean[N][N];
			
			for(int i=0; i<N; i++) {
				String s=br.readLine();
				for(int j=0; j<N; j++) {
					map[i][j]=s.charAt(j)-'0';
					ans[i][j]=Integer.MAX_VALUE;
				}
			}
			
			ans[0][0]=map[0][0];
			
            //문제에 시작점과 도착점은 무조건 0이라 하였으므로, 0으로 넘겼다.
			dijkstra(new Pos(0,0,0));
			
			System.out.printf("#%d %d\n",t,ans[N-1][N-1]);
			
		}
				
	}
	private static void dijkstra(Pos pos) {
		int[] dx= {0,0,1,-1};
		int[] dy= {1,-1,0,0};
		
		PriorityQueue<Pos> pq = new PriorityQueue<Pos>();
		
		pq.add(pos);
		
		while(!pq.isEmpty()) {
			Pos p = pq.poll();
			int x=p.x;
			int y=p.y;
			
			for(int i=0; i<4; i++) {
				int nx=x+dx[i];
				int ny=y+dy[i];
				
				if(nx<0||nx>=N||ny<0||ny>=N||visited[nx][ny]) continue;
				if(ans[nx][ny]>ans[x][y]+map[nx][ny]) {
					ans[nx][ny]=ans[x][y]+map[nx][ny];
					visited[nx][ny]=true;
					pq.add(new Pos(nx,ny,ans[nx][ny]));
					
				}
				
			}
			
		}
	}
	static class Pos implements Comparable<Pos>{
		int x;
		int y;
		int w;
		
		public Pos(int x, int y, int w) {
			super();
			this.x = x;
			this.y = y;
			this.w = w;
		}

		@Override
		public int compareTo(Pos o) {
			// TODO Auto-generated method stub
			return this.w-o.w;
		}
		
	}

}

https://java-is-happy-things.tistory.com/33

[Java] BJ4485_녹색옷입은애가젤다지