[프로그래머스] 보급로 for JAVA

 

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

SW Expert Academy

 

 

 

딱 보고 전형적인 BFS 문제로 추정했다.

 

 

(0,0) ~ (N-1, N-1)까지 가는 최소 비용을 구하는 문제이다.

 

 

 

대신 가는 곳마다 weight가 있고 그 자리에 갈 수 있는 최소 weight를 구해야 하므로... 넘넘 까다로웠다!

 

 

처음에는 그냥 BFS 구현 딱 하고 visited 처리 해줬는데 이렇게 하면 구불구불한 길이 정답일 때가 구현이 안돼서

 

매우매우 고민하다가... 정말 귀찮아서 하기 싫었던 priority queue로 구현하기로 했다.

 

 

최소비용 하면 다익스트라!!!! 기억하자....

 

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution{
	
	static class Node implements Comparable<Node>{
		int x, y, weight;

		public Node(int x, int y, int weight) {
			this.x = x;
			this.y = y;
			this.weight = weight;
		}

		@Override
		public String toString() {
			return "Node [x=" + x + ", y=" + y + ", weight=" + weight + "]";
		}

		@Override
		public int compareTo(Node o) { // 가중치 오름차순
			return Integer.compare(this.weight, o.weight);
		}
		
		
	}
	
	static int N;
	static int[][] map, newMap;

	public static void main(String[] args) throws Exception{
		StringBuilder sb = new StringBuilder();
		System.setIn(new FileInputStream("res/input_보급로.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			
			map = new int[N][N];
			for(int i=0; i<N; i++) {
				char in[] = br.readLine().toCharArray();
				for(int j=0; j<N; j++) {
					map[i][j] = in[j]-'0';
				}
			}
			newMap = new int[N][N];
			for(int i=0; i<N; i++)
				Arrays.fill(newMap[i], 9*N*N);
			
			newMap[0][0] = 0;
			
			
			/// 입력 끝 ///
			bfs(new Node(0, 0, 0));
			sb.append("#").append(tc).append(" ").append(newMap[N-1][N-1]).append('\n');
			
		}
		System.out.println(sb.toString());

	}
	static int[] dx = {0,1, 0, -1};
	static int[] dy = {1,0, -1, 0};
	
	private static void bfs(Node start) {
		PriorityQueue<Node> queue = new PriorityQueue<>(); // 다익스트라
		queue.add(start);
		
		while(!queue.isEmpty()) {
			
			Node out = queue.poll();
			int i = out.x;
			int j = out.y;
			
			if(i==N-1 && j==N-1) break;
			
			for(int d=0; d<4; d++) {
				int nx = i + dx[d];
				int ny = j + dy[d];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
				if(newMap[nx][ny] <= newMap[i][j] + map[nx][ny]) continue;
				newMap[nx][ny] = newMap[i][j] + map[nx][ny];
					
				queue.add(new Node(nx, ny, newMap[nx][ny]));
			}
		}
		
		
	}

}

 

 

이렇게 하면 가중치가 작은 map 순서대로 poll 되면서 i==N-1 이고 j==N-1인 곳에 당도하면 리턴하고 끝난다.

 

 

아니면 그냥 Queue를 쓰고 (N-1, N-1) 위치에 올 수 있는 min값을 리턴하는 방식을 쓸 수도 있음!

 

 

 

남의 코드도 봤는데 DFS를 쓰고 가지치기를 해도 풀 수 있는 문제이다.

 

 

 

 

 

 

 

코테 풀 때 정신차리고 풀자.....