[백준 - 골드] 1261. 알고스팟

이번 주의 문제

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

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

생각해본 풀이

일단 최소 몇 개 부순다는 것은 가장 적은 비용을 지불하라는 뜻이니까, 다익스트라를 사용하면 어떨까?

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

public class 알고스팟_1261 {

	static int[] dr = { 1, 0, -1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	
	static class Room implements Comparable<Room> {
		int r;
		int c;
		int cost;
		
		public Room(int r, int c, int cost) {
			this.r = r;
			this.c = c;
			this.cost = cost;
		}

		@Override
		public int compareTo(Room o) {
			return Integer.compare(this.cost, o.cost);
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//반대로 받았어야 했다!!!
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		int[][] spot = new int[N+1][M+1]; //1부터 시작
		
		for(int r = 1; r <= N; r++) {
			String str = br.readLine();
			for(int c = 1; c <= M; c++) {
				spot[r][c] = str.charAt(c - 1) - '0';
			}
		} //입력
		
		int[][] dist = new int[N+1][M+1];
		
		int INF = Integer.MAX_VALUE; //무한
		
		for(int r = 1; r <= N; r++) {
			for(int c = 1; c <= M; c++) {
				dist[r][c] = INF;
			}
		}
		
		dist[1][1] = 0; //시작지점
		
		PriorityQueue<Room> pq = new PriorityQueue<>();
		pq.offer(new Room(1, 1, 0));
		
		while(!pq.isEmpty()) {
			Room now = pq.poll();
			int nowR = now.r;
			int nowC = now.c;
			
			
			for(int d = 0; d < 4; d++) {
				int nextR = nowR + dr[d];
				int nextC = nowC + dc[d];
				
				if(nextR <= 0 || nextR > N || nextC <= 0 || nextC > M) continue;
				
				if(dist[nextR][nextC] > dist[nowR][nowC] + spot[nextR][nextC]) {
					dist[nextR][nextC] = dist[nowR][nowC] + spot[nextR][nextC];
					
					pq.offer(new Room(nextR, nextC, dist[nextR][nextC]));
				}
			}
		}
		
		System.out.println(dist[N][M]);
	}
}

함께 보면 좋은 알고리즘

다익스트라 알고리즘

최단 거리를 구할 수 있는 알고리즘 중 하나로, BFS(너비 우선 탐색)과의 차이점은 각 노드들 사이에 가중치에 존재한다는 점이다. 단, 이 가중치가 음수일 때는 사용할 수 없다. 이 알고리즘에서는 DP(동적 계획법) 요소도 작용하는데, 모든 노드들을 돌며, 최소 비용들을 갱신해 사용하기 때문이다.

이 알고리즘은 출발, 도착으로 구성된 2차원 인접배열(배열, 인접리스트로 구현 가능), 우선순위 큐(힙) 두 개를 활용하여 구현할 수 있다.

위의 문제는 인접 배열로 선언하고, 이를 우선순위 큐를 이용해 갱신함으로써 구현하였다.