[백준 1261번/JAVA] 알고스팟 (문제 풀이, 코드)

알고스팟

[문제]

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 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)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

[풀이]

(1,1) => (N,M) 까지의 최단 거리를 구하는 알고리즘 문제.

가중치가 있는 그래프의 최단 거리는 다익스트라 알고리즘을 이용하면 된다.

 

다익스트라 알고리즘이란 ?

모든 정점까지의 가중치(비용,시간.. 등)을 최대값을 주고 시작 정점을 고른다.

시작 정점은 0.

시작정점에서 방문할 수 있는 모든 정점까지의 가중치를 업데이트, 시작 정점은 방문처리한다. ( 표에 실수가 있다. 정점 5는 12가 되어야한다. )

가중치가 작은 정점을 골라서 똑같이 해준다.

정점을 업데이트 할 때, 시작점->정점4(INF) 보다는 시작점->정점2->정점4(3+5=8) 이 더 작으므로 8로 업데이트 해주는 것이다.

 

이하 생략한다.

 

그렇게 하여 최단 거리를 구하는 알고리즘.

그리고 가장 가중치가 낮은 정점을 방문하여 해당 정점이 갈 수 있는 모든 정점까지의 거리를 업데이트한다.

 

[내 코드 알고리즘]

가중치가 작은 정점을 고를 때 우선순위 큐(Priority Queue)를 사용한다는 점을 추가하면 위와 같다.

 

1. map(0과 1로 이루어진 미로), v(INF와 가중치를 담을 배열), visited를 만들고 값을 넣어준다.

2. 시작정점(1,1)의 가중치를 0으로 초기화하고 방문 표시한다. 그리고 큐에 담는다.

3. 여기서부터는 큐가 빌 때까지 반복분이 시행된다.

     - 큐에서 값을 뽑아온다.

     - 갈 수 있는 다음 위치가 어딘지 확인한다.

     - 다음 위치가 가진 부서진 벽 수(v)와 현 위치에서 다음 위치로 갈 때까지 부서진 벽 수(v)를 비교한다.

     - 현 위치에서 다음 위치로 갈 때까지 부서진 벽 수의 크기가 작을때만!!! 큐에 넣는다. (작거나 같다고 해버리면 메모리 초과가 난다.)

 

[코드]

package m;

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

class maze implements Comparable<maze>{
	int i,j,b;
	maze(int i, int j, int b){ // 좌표1,좌표2,부순벽
		this.i = i;
		this.j = j;
		this.b= b;
	}
	public int compareTo(maze t) {
		return this.b <= t.b ? -1: 1;
	}
}

public class AlgoSpot_1261 {
	public static void main(String args[]) throws IOException{
		/* 입력 */
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] st = br.readLine().split(" ");
		int INF = 1000000;
		int M = Integer.parseInt(st[0]); // 가로길이
		int N = Integer.parseInt(st[1]); // 세로길이
		int[][] map = new int[N+1][M+1]; // 미로
		int[][] v = new int[N+1][M+1];
		boolean[][] visited = new boolean[N+1][M+1]; // 방문 여부
		PriorityQueue<maze> pq = new PriorityQueue<>();
		for(int i=1; i<N+1; i++) {
			st = br.readLine().split("");
			for(int j=1; j<M+1; j++) {
				map[i][j] = Integer.parseInt(st[j-1]);
				v[i][j] = INF;
			}
		}
		
		int[] dx = {0,0,-1,1};
		int[] dy = {-1,1,0,0};
		
		/* 탐색 */
		visited[1][1] = true;
		v[1][1] = 0;
		pq.add(new maze(1,1,0));
		
		while(!pq.isEmpty()) {
			maze pos = pq.poll(); // 현재 위치
			int x = pos.i; int y = pos.j;
			//System.out.println(x+","+y);
			visited[x][y]=true; 
			// 현재 위치에서 갈 수 있는 곳
			for(int i=0;i<4;i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx>0 && nx<N+1 && ny>0 && ny<M+1 && !visited[nx][ny]) {
					if(map[nx][ny]==0) { // 다음 위치가 벽이 아닌 경우
						if(v[nx][ny] > pos.b) {
							pq.add(new maze(nx,ny,pos.b));
							v[nx][ny] = pos.b;
						}
					}
					else{ // 다음 위치가 벽인 경우
						if(v[nx][ny] > pos.b+1){
							pq.add(new maze(nx,ny,pos.b+1));
							v[nx][ny] = pos.b+1;
						}
					}
				}
			}
		}
		
		System.out.println(v[N][M]);
		
	}
}

[난관]

처음에 간단하게 bfs+우선순위큐 결합으로 모든 정점을 방문하여 해결하려다보니 메모리초과가 났다.

다익스트라 알고리즘에 맞게 조건을 추가하여 메모리 초과를 피할 수 있었다.

 

제 코드는 GitHub에 업로드 되어 있습니다. 무단 배포를 금합니다.

https://github.com/MOBUMIN/BJalgorithm/blob/master/01000-01999/AlgoSpot_1261.java

MOBUMIN/BJalgorithm