[백준] 1261 알고스팟

문제

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

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

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

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

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

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

접근 방법

문제를 접하고 가장 먼저 재귀 함수를 배울때 흔히 예제로 사용하는 미로찾기 알고리즘 이었다. 미로찾기 알고리즘과 벽을 깨는 횟수를 비용으로 하여 우선순위 큐를 사용하면 해결될 것 이라 판단하여 작성했다.

 

그리고 다른 사람들의 풀이를 찾아보니 다익스트라 알고리즘을 사용하여 해결한 것이 대부분이었고, 재귀 함수 호출 오버헤드가 발생하지 않기 때문에 내가 작성한 알고리즘 보다 효율적이라 생각된다.

 

기본적인 다익스트라 알고리즘을 사용하되 깨부수는 벽의 수를 비용으로 설정하면 쉽게 풀린다.

 

소스 코드

자바 - 재귀 호출

package Path;

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

public class Path_1261 {
	public static class Point implements Comparable<Point>{
		int col;
		int row;
		int cost;
		
		Point(int col, int row, int cost){
			this.col = col;
			this.row = row;
			this.cost = cost;
		}
		@Override
		public int compareTo(Point o) {
			return Integer.compare(this.cost, o.cost);
		}
		
	}
	static PriorityQueue<Point> pq;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] line = br.readLine().split(" ");
		
		int M = Integer.valueOf(line[0]);
		int N = Integer.valueOf(line[1]);
		pq = new PriorityQueue<>();
		
		int[][] graph = new int[N][M];
		
		for(int i=0;i<N;i++) {
			line = br.readLine().split("");
			for(int j=0;j<line.length;j++) {
				graph[i][j] = Integer.valueOf(line[j]);
			}
		}
		
		pq.offer(new Point(0, 0, 0));
		search(graph, pq.poll(), N, M);
	}
	public static void search(int[][] graph, Point p, int n, int m) {
		if(graph[p.row][p.col] == 2) {
			return;
		}
		if(p.col == m-1 && p.row == n-1) {
			graph[p.row][p.col] = 2;
			System.out.println(p.cost);
			return;
		}
		int temp = 0;
		if(graph[p.row][p.col] == 1) {
			temp = 1;
		}
		graph[p.row][p.col] = 2;
		
		if(p.col  + 1 >= 0 && p.col+1 < m)
			pq.offer(new Point(p.col+1, p.row, p.cost + temp));
		if(p.col  - 1 >= 0 && p.col - 1 < m)
			pq.offer(new Point(p.col-1, p.row, p.cost + temp));
		if(p.row + 1 >= 0 && p.row + 1 < n)
			pq.offer(new Point(p.col, p.row+1, p.cost + temp));
		if(p.row - 1 >= 0 && p.row - 1 < n	)
			pq.offer(new Point(p.col, p.row-1, p.cost + temp));
		
		while(!pq.isEmpty()) {
			search(graph, pq.poll(), n ,m);
		}
	}

}

자바 - 다익스트라

package Path;

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

public class Path_1261_2 {
	public static class Point implements Comparable<Point>{
		int col;
		int row;
		int cost;
		
		Point(int col, int row, int cost){
			this.col = col;
			this.row = row;
			this.cost = cost;
		}
		@Override
		public int compareTo(Point o) {
			return Integer.compare(this.cost, o.cost);
		}
		
	}
	static PriorityQueue<Point> pq;
	static int[] dCol = {1, -1, 0, 0};
	static int[] dRow = {0, 0, 1, -1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] line = br.readLine().split(" ");
		
		int M = Integer.valueOf(line[0]);
		int N = Integer.valueOf(line[1]);
		pq = new PriorityQueue<>();
		
		int[][] graph = new int[N][M];
		int[][] dist = new int[N][M];
		
		
		for(int i=0;i<N;i++) {
			line = br.readLine().split("");
			for(int j=0;j<line.length;j++) {
				graph[i][j] = Integer.valueOf(line[j]);
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				dist[i][j] = Integer.MAX_VALUE;
			}
		}
		
		search(graph, dist, M, N);
	}
	public static void search(int[][] graph, int[][] dist, int M, int N) {
		pq.offer(new Point(0, 0, 0));
		dist[0][0] = 0;
		
		while(!pq.isEmpty()) {
			Point p = pq.poll();
			
			if(p.col == M-1 && p.row == N-1) {
				System.out.println(p.cost);
				return;
			}
			
			
			
			for(int i=0;i<4;i++) {
				int nCol = p.col + dCol[i];
				int nRow = p.row + dRow[i];
				
				if(nCol >= 0 && nCol < M && nRow >= 0 && nRow < N) {
					if(dist[nRow][nCol] > dist[p.row][p.col] + graph[nRow][nCol]) {
						dist[nRow][nCol] = dist[p.row][p.col] + graph[nRow][nCol];
						pq.offer(new Point(nCol, nRow, dist[nRow][nCol]));
					}
				}
			}
		}
	}

}

파이썬

import sys
import heapq

readline = sys.stdin.readline

def main():
    # M: column, N: row
    M, N = map(int, readline().split())
    
    graph = [[] for _ in range(N)]

    # Build Graph
    for i in range(N):
        line = readline().strip()
        graph[i] = [int(l) for l in line]
    
    bfs(graph, M, N)

def bfs(graph, M , N):
    dCol = [1, -1, 0, 0]
    dRow = [0, 0, 1, -1] 
    hq = []
    dist = [[sys.maxsize] * M for _ in range(N)]
    heapq.heappush(hq, [0, 0, 0])
    dist[0][0] = 0

    while hq:
        cost, col, row = heapq.heappop(hq);
        
        if col == M-1 and row == N-1:
            print(cost)
            return
        for i in range(4):
            new_col = col + dCol[i]
            new_row = row + dRow[i]
            
            if(new_col >= 0 and new_col < M and new_row >= 0 and new_row < N):
               
                if(dist[new_row][new_col] > graph[new_row][new_col] + dist[row][col]):
                    dist[new_row][new_col] = graph[new_row][new_col] + dist[row][col]
                    heapq.heappush(hq, [dist[new_row][new_col], new_col, new_row])
    

if __name__ == '__main__':
    main()