[백준] 1261번 - 알고스팟 (Java)

풀이

키워드

• 다익스트라

  다익스트라로 푸는 것을 안다면 그렇게 어려운 문제는 아니였다. 그러나 다익스트라로 풀어야 한다는 것을 눈치채는 것이 문제라면 문제인 그런 유형이였다. 우선 그래프 탐색에는 유명한 3가지 DFS, BFS, Dijkstra가 있다.

  

<BFS, DFS VS Dijkstra>

  우선 대부분의 문제에서 2차원 형식의 지도(?)처럼 주어지면 대개 DFS/BFS로 푸는 경우가 많다. 반대로, Dijkstra의 경우 대부분 이렇게 2차원 지도로 주어지지 않고 각 노드간의 연결 정보와 그 가중치가 주어진다. 이렇게 주어지는 이유는, DFS/BFS와 Dijkstra의 가장 큰 차이점은 노드간 가중치가 같은지 여부이기 때문이다.

  DFS/BFS의 경우 모든 노드간의 가중치가 같고, 우리가 찾아내야 하는 정답의 기준은 "얼마나 적은 수의 노드를 거쳤는가"이다. 그러나 Dijkstra의 경우 노드간의 가중치가 상이하며 심지어 연결정보가 따로 주어지는 경우도 있다. 또한 우리가 찾아내야 하는 정답의 기준은 "얼마나 적은 가중치의 합으로 목적지에 도달하였는가"이다.

  이를 고려하며 문제를 보면, 문제에서는 얼마나 빨리 목적지에 도달하였는지보다는, 얼마나 적은 벽을 부수고서 목적지에 도달하였는지를 기준으로 삼아야 한다는 것을 쉽게 알 수 있다. 그리고 벽을 얼마나 부쉈는지는, 노드가 0을 지나치는지 1을 지나치는지에 따라 달라진다. 즉 (현재노드) -> ("0"인 노드) 에서의 가중치는 0이지만, (현재노드) -> ("1"인 노드) 에서의 가중치는 1이라고 할 수 있다. 또한 연결정보도 각 노드의 위, 우측, 아래, 좌측 임이 주어졌다. 따라서 이를 통해 다익스트라를 통해 풀 수 있음을 알 수 있다.

 

<Dijkstra>

  구성 : 가중치 및 연결정보, dist[], PriorityQueue, public Class implements Comparable<T>

  과정

1. dist의 모든 원소를 Integer.MAX_VALUE로 초기화한다.
2. PriorityQueue에 시작점의 정보를 넣고, dist[시작점] = 0 으로 세팅한다.
3. PriorityQueue가 빌 때까지 반복한다.
   • 현재 노드를 꺼낸다.
   • 현재 노드와 연결되는 노드들을 보고, (현재 노드에서 다음 노드로 갈 때까지 합한 가중치의 합) 보다 dist[다음노드]가 크다면, 이 가중치의 합으로 dist[다음노드]를 갱신하고, 이 다음노드를 PriorityQueue에 넣는다.
   • 만약 dist[다음노드]가 더 작다면 continue 한다.

---

코드

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

public class Main {
	static int N, M;
	static char [][] arr;
	static int [][] dist;
	static int [] dy = {-1, 0, 1, 0};
	static int [] dx = {0, 1, 0, -1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String [] inputs = br.readLine().split(" ");
		M = Integer.parseInt(inputs[0]);
		N = Integer.parseInt(inputs[1]);
		arr = new char[N][M];
		dist = new int[N][M];
		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine().toCharArray();
			Arrays.fill(dist[i], Integer.MAX_VALUE);
		}
		dijkstra();
		
		System.out.print(dist[N-1][M-1]);
	}
	
	public static void dijkstra() {
		PriorityQueue<Point> pq = new PriorityQueue<Point>();
		dist[0][0] = 0;
		pq.offer(new Point(0, 0, 0));
		while(!pq.isEmpty()) {
			Point cur = pq.poll();
			
			for (int i = 0; i < 4; i++) {
				int nextY = cur.y + dy[i];
				int nextX = cur.x + dx[i];
				int nextBroken = cur.broken;
				if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
					continue;
				if (arr[nextY][nextX] == '1')
					nextBroken++;
				if (dist[nextY][nextX] > nextBroken) {
					dist[nextY][nextX] = nextBroken;
					pq.offer(new Point(nextY, nextX, nextBroken));
				}
			}
		}
	}
	
	static class Point implements Comparable<Point>{
		int y;
		int x;
		int broken;
		
		public Point(int y, int x, int broken) {
			this.y = y;
			this.x = x;
			this.broken = broken;
		}
		
		@Override
		public int compareTo(Point p) {
			return this.broken - p.broken;
		}
	}
}

 

---

출처 : https://www.acmicpc.net/problem/1261

1261번: 알고스팟