G1261.알고스팟

문제

제출 코드

• 사용 알고리즘 : 다익스트라

우선순위 큐를 사용한 다익스트라를 구현하여 풀이했다.

3달 전에 풀었다가 실패하고, 다시 시도한 문제이다.

그때도 dfs를 사용하여 풀었다가 시간초과, 메모리 초과가 났고, 이번에도 초반에 동일하게 풀어 실패했었다.

우선순위 큐를 사용하여 다음 방문할 노드를 큐에서 꺼낼때, 출발점에서부터 해당 노드까지 최소비용을 가지는 노드부터 꺼내도록 했다.

최소신장트리 문제이기에 다익스트라로 다시풀었으나, 방문체크를 하는 순서의 미묘한 차이로 메모리 초과가 났다. 큐에 넣고 난 후 꺼내는 과정에서 방문체크를 하면서 큐 안에 중복값의 노드가 다량으로 들어가 메모리 초과가 난 듯 해서, 넣기 전에 방문체크를 해주도록 변경했다.

package gold;

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

public class G1261_algospot {

	static int N, M;
	static char[][] map;
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	static int[][] weight;

	static class Node implements Comparable<Node>{
		int i, j;
		Node(int i, int j){
			this.i = i;
			this.j = j;
		}
		// 우선순위 큐 안에서의 우선순위 설정. 해당 노드까지 가는데 소요되는 최소비용끼리 비교한다
		@Override
		public int compareTo(Node o) {
			return weight[this.i][this.j] - weight[o.i][o.j];
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		map = new char[N][M];
		for(int i=0; i<N; i++) map[i] = br.readLine().toCharArray();

		weight = new int[N][M];
		for(int i=0; i<N; i++) Arrays.fill(weight[i], -1);
		weight[0][0] = 0;

		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		queue.add(new Node(0, 0));
		boolean[][] visit = new boolean[N][M];
		visit[0][0] = true;

		while(!queue.isEmpty()) {
			Node now = queue.poll();
			for(int d=0; d<4; d++) {
				int ni = now.i + di[d];
				int nj = now.j + dj[d];
				if(ni<0 || ni>=N || nj<0 || nj>=M || visit[ni][nj]) continue;

				if(weight[ni][nj]==-1) weight[ni][nj] = weight[now.i][now.j] + (map[ni][nj]-'0');
				else weight[ni][nj] = Math.min(weight[now.i][now.j] + (map[ni][nj]-'0'), weight[ni][nj]);
				queue.add(new Node(ni, nj));
				visit[ni][nj] = true;
			}
		}
		System.out.println(weight[N-1][M-1]);
	}
}