백준 알고스팟

다익스트라 알고리즘으로 풀이할 수 있는 문제

1번과 2번 코드의 차이점은 2가지가 있다.

pq.add(new Node(0,0,0));
cost[0][0] = 0;

2번째 코드의 45번 라인이다.

내 생각에는 Node(0,0,0)과 Node(0,0,map[0][0])은 동일하기 때문에 문제가 아니지만 cost[0][0]=0 으로 초기화해준 부분이 키인것 같다.

방문배열을 별도로 사용하지 않기 때문에 cost배열은 방문배열의 역할도 겸하고 있다. 그렇게 때문에 0으로 초기화하지 않으면 다시 [0][0]으로 되돌아 오는 경우가 발생할 때, 방문이 체크되지 않았기 때문에 잘못된 경로를 추가하게 될 수 있다. 따라서 0으로 초기화하여 방문을 체크함으로써 올바른 비용을 계산할 수 있도록 했다.

 

1. 틀린 코드

import java.util.*;
import java.io.*;

public class Main {
	
	static class Node{
		int r;
		int c;
		int value;
		
		Node(int r, int c, int value){
			this.r = r;
			this.c = c;
			this.value = value;
		}
	}
	
	static int N, M;
	static int[][] map, cost;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[M][N];
		cost = new int[M][N];
		for(int i = 0; i < M; i++) {
			char[] tmp = br.readLine().toCharArray();
			for(int j = 0; j < N; j++) {
				map[i][j] = tmp[j]-'0';
				cost[i][j] = Integer.MAX_VALUE;
			}
		}
		
		dijkstra();
		System.out.println(cost[M-1][N-1]);

	}

	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	private static void dijkstra() {
		PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2)->(o1.value-o2.value));
		pq.add(new Node(0,0,map[0][0]));
		
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			int r = now.r;
			int c = now.c;
			int value = now.value;
			
			for(int d = 0; d < 4; d++) {
				int nr = r+dr[d];
				int nc = c+dc[d];
				
				if(!check(nr,nc)) continue;
				if(cost[nr][nc] <= value+map[nr][nc]) continue;
				cost[nr][nc] = value+map[nr][nc];
				pq.add(new Node(nr,nc,cost[nr][nc]));
			}
		}
	}
	private static boolean check(int r, int c) {
		return r>=0 && r<M && c>=0 && c<N;
	}
}

 

 

2. 맞은 코드

import java.util.*;
import java.io.*;

public class Main {
	
	static class Node{
		int r;
		int c;
		int value;
		
		Node(int r, int c, int value){
			this.r = r;
			this.c = c;
			this.value = value;
		}
	}
	
	static int N, M;
	static int[][] map, cost;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[M][N];
		cost = new int[M][N];
		for(int i = 0; i < M; i++) {
			char[] tmp = br.readLine().toCharArray();
			for(int j = 0; j < N; j++) {
				map[i][j] = tmp[j]-'0';
				cost[i][j] = Integer.MAX_VALUE;
			}
		}
		
		dijkstra();
		System.out.println(cost[M-1][N-1]);

	}

	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	private static void dijkstra() {
		PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2)->(o1.value-o2.value));
		pq.add(new Node(0,0,0));
		cost[0][0] = 0;
		
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			int r = now.r;
			int c = now.c;
			int value = now.value;
			
			if(value > cost[r][c]) continue;
			
			for(int d = 0; d < 4; d++) {
				int nr = r+dr[d];
				int nc = c+dc[d];
				
				if(!check(nr,nc)) continue;
				if(cost[nr][nc] <= value+map[nr][nc]) continue;
				cost[nr][nc] = value+map[nr][nc];
				pq.add(new Node(nr,nc,cost[nr][nc]));
			}
		}
	}
	private static boolean check(int r, int c) {
		return r>=0 && r<M && c>=0 && c<N;
	}
}