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

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

SW Expert Academy

[코드]

import java.util.*;

class Node_보급로 implements Comparable<Node_보급로>{
	int x,y,time;
	
	public Node_보급로(int x, int y, int time) {
		this.x=x;
		this.y=y;
		this.time=time;
	}

	// 복구 시간이 더 적게 걸리는 노드 먼저 출력
	public int compareTo(Node_보급로 o) {
		// TODO Auto-generated method stub
		return this.time-o.time;
	}
}
public class 보급로 {
	static int[][] map;
	static boolean[][] visited;
	static int min,n;
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		
		for(int k=1;k<=t;k++) {
			n=sc.nextInt();
			
			map=new int[n][n];
			visited=new boolean[n][n];
			
			min=Integer.MAX_VALUE;
			
			for(int i=0;i<n;i++) {
				String str=sc.next();
				for(int j=0;j<n;j++) {
					map[i][j]=str.charAt(j)-'0';
				}
			}
			
			BFS();
			System.out.println("#"+k+" "+min);
		}
	}
	
	static void BFS() {
		PriorityQueue<Node_보급로> pq=new PriorityQueue<>();
		pq.add(new Node_보급로(0,0,0)); // (0,0)에서 시작, 초기 복구비용은 0
		visited[0][0]=true;
		
		while(!pq.isEmpty()) {
			Node_보급로 now=pq.poll();
			
			// 목적지에 도달했다면 최소 복구 시간 갱신
			if(now.x==n-1&&now.y==n-1)
				min=Math.min(min, now.time);
			
			for(int i=0;i<4;i++) {
				int nx=now.x+dx[i];
				int ny=now.y+dy[i];
				
				if(nx<0|ny<0||nx>=n||ny>=n||visited[nx][ny])
					continue;
				
				visited[nx][ny]=true; // 방문처리
				pq.add(new Node_보급로(nx,ny,now.time+map[nx][ny])); // 복구시간 더해주기
			}
		}
	}
}

 

[고찰]

 이번 문제는 읽어봤을 때 딱 BFS 알고리즘을 사용해야 함을 알 수 있었다. 이때, 복구시간이 더 적게 드는 노드를 먼저 탐색하기 위해 우선순위 큐를 사용하는 것만 주의하면 됐다.