[JAVA] 백준 1261 : 알고스팟

문제

1261번: 알고스팟

 

해결 방법

다익스트라 알고리즘을 사용해서 풀어야 합니다.

다익스트라 알고리즘은 A에서 B로 가는 것의 최단 거리를 구할 때 주로 사용합니다.

이 문제에서는 시작 지점과 끝 지점이 지정되어있고, 구해야 하는 벽을 부순 횟수가 

음수로 존재하지 않기 때문에 사용이 가능합니다.

 

코드는 다익스트라 알고리즘을 그대로 구현한 것이라 따로 설명하진 않겠습니다.

 

아래 링크의 분이 잘 설명해두셔서 참조 남깁니다.

[알고리즘/자바] 다익스트라 알고리즘 (Dijkstra Algorithm)

 

코드

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

public class Main {
	static int dist[][];
	static int array[][];
	static int N, M;
	static int result = 0;
	
	static int dx[] = {0, 0, 1, -1};
	static int dy[] = {-1, 1, 0, 0};
	
	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());
		
		array = new int[N][M];
		for (int i = 0; i < N; i++) {
			String a = br.readLine();
			for (int j = 0; j < M; j++) {
				array[i][j] = a.charAt(j) - '0';
				// char형을 int로 변환할 때 위와 같이 사용
			}
		}
		
		dist = new int[N][M];
		for (int i = 0; i < N; i++) {
			Arrays.fill(dist[i],Integer.MAX_VALUE);
			// dist 배열을 모두 최댓값으로 지정
		}
		
		
		dijkstra();
		
		System.out.println(result);
	
	}
	
	static void dijkstra() {
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.offer(new Node(0, 0, 0));
		dist[0][0] = 0;
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			if (node.x == N - 1 && node.y == M - 1) {
				result = node.broken;
                // 가장 먼저 목적지에 도착한 값이 최솟값이기 때문에
                // 바로 return 해주면 됩니다
				return;
			}
			
			for (int i = 0; i < 4; i++) {
				int newX = node.x + dx[i];
				int newY = node.y + dy[i];
				
				if (newX >= 0 && newX < N && newY >=0 && newY < M) {
					// 1인 벽을 지나갈 때 부숴야하는 횟수가 1 증가하기에 아래와 같이 조건 설정 가능
					if (dist[newX][newY] > dist[node.x][node.y] + array[newX][newY]) {
						dist[newX][newY] = dist[node.x][node.y] + array[newX][newY];
						
						q.offer(new Node(newX, newY, dist[newX][newY]));
					}
				}
			}
		}
		
	}
}

class Node implements Comparable<Node> {
	int x;
	int y;
	int broken;
	
	Node (int x, int y, int broken) {
		this.x = x;
		this.y = y;
		this.broken = broken;
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return broken - o.broken;
	}
}