SW_1249_보급로

1

구분: 그래프 이론, 그래프 탐색, 너비 우선 탐색
언어: Java
전략

BFS와 다익스트라를 결합했다고 생각하자 

나의 위치까지 오는데 걸리는 최소값을 저장하는 2차원 배열을 생성하자

탐색을 하면서 내 자리까지 오는데 최소값이 현재 내 비용과 여기까지 오는데 걸리는 최소값보다 크다면 갱신한다.

---

2.코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
	static class Node{
		int y, x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc<=T; tc++) {
			int n = Integer.parseInt(br.readLine());//배열의 크기 
			int[][] map = new int[n][n];//전체 배열을 담을 배열
			int[][] d = new int[n][n];//값이 조정되는 것을 받을 배열
			
			for(int i = 0; i<n; i++) {
				String str = br.readLine();
				for(int j = 0; j<n; j++) {
					map[i][j] = str.charAt(j)-'0';
					d[i][j] = Integer.MAX_VALUE;
				}
			}
				
			//큐를 이용하여 값들을 넣는다.  
			Queue<Node> q = new LinkedList<>();
			
			d[0][0] = 0;//시작점 - 비용을 0으로 한다
			q.add(new Node(0,0));//큐에 넣는다
			
			//4방 탐색
			int[] dx = {1, -1, 0, 0};
			int[] dy = {0, 0, 1, -1};
			
			while(!q.isEmpty()) {
				Node node = q.poll();
				int qx = node.x;
				int qy = node.y;
				
				for(int dd = 0; dd<4; dd++) {
					int nx = qx + dx[dd];
					int ny = qy + dy[dd];
					
					//범위 체크
					if(nx<0||ny<0||nx>=n||ny>=n)
						continue;
					
					//map의 값+ 지그까지 최소값 이 그 자리의 최고값보다 작으면 갱신
					if(d[ny][nx]>map[ny][nx]+d[qy][qx]) {
						d[ny][nx] = map[ny][nx] + d[qy][qx];
						q.add(new Node(ny,nx));
					}
				}
			}
			
			
			//도착점
			System.out.println("#"+tc+" "+d[n-1][n-1]);
			
		}//test
		
	}//main
	
	
}

---

3

백준에서 비슷한 문제를 풀어보아서 금방 풀 수 있었다.