[JAVA]SWEA_1249_보급로

문제링크

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

SW Expert Academy

 

 

 

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

public class Solution {

	static int N;
	static int map[][];
	static int isVisited[][];
	static PriorityQueue<Node> q;
	static int dx[] = {0,0,-1,1};
	static int dy[] = {-1,1,0,0};
	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 t=0;t<T;t++) {
			N = Integer.parseInt(br.readLine());
			
			map = new int[N][N];
			isVisited = 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';
					isVisited[i][j] = Integer.MAX_VALUE;
				}
			}
			
			//for(int i=0;i<N;i++) System.out.println(Arrays.toString(map[i]));
//			isVisited[0][0] = true;
//			dfs(0,0);
			q = new PriorityQueue<>();
			
			q.offer(new Node(0,0,0));
			bfs();
			System.out.println("#"+(t+1)+" "+isVisited[N-1][N-1]);
		}
		
	}
	
	static void bfs() {
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				
				if(nx<0 || ny<0 || nx>=N || ny>=N ) continue;
				
				if(isVisited[nx][ny]>node.result+map[nx][ny]) {
					isVisited[nx][ny]  = node.result + map[nx][ny];
					q.offer(new Node(nx,ny,node.result+map[nx][ny]));
				}
				
			}
		}
	}
	
	static class Node implements Comparable<Node>{
		int x,y;
		int result;
		public Node(int x, int y, int result) {
			super();
			this.x = x;
			this.y = y;
			this.result = result;
		}
		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return this.result-o.result;
		}
		
		
	}
}

 

처음에 접근했을 때는 사방향 탐색하면서 그 중에서 작은 값만 계속 큐에 넣어주는 방법을 생각해서 풀었는데 이렇게 접근할 시 제일 작은 값을 따라 끝까지 갔는데 마지막 값이 100000 같이 매우 큰 숫자일 경우 소용이 없었다.

 

결론은 모든 경우의 수? 를 다 탐색해야하는 것 같다.