문제링크
https://www.acmicpc.net/problem/1261
1261번: 알고스팟
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미
www.acmicpc.net
문제설명
문제
알고스팟 운영진이 모두 미로에 갇혔다. 미로는 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)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.
제한사항
| 제한시간 | 메모리제한 |
| 1초 | 128MB |
출처 - www.acmicpc.net
문제풀이
👨🏻💻 핵심 스킬 👨🏻💻
큐 2개를 이용한 BFS
문제를 요약하면 원래 뚫려있는 길을 갈 수 있고 길이 안뚫려있으면 1을 소모하여 갈 수 있습니다. 이렇게 갈 때 맨 끝쪽 배열로 벽을 최대한 조금 뚫고 갈 때의 비용을 물어보는 문제입니다.
이 문제는 간선의 가중치가 0과 1로 서로 다른 문제입니다. 이미 뚫려있는 길을 가는 경우는 0이고 벽을 뚫고가야하는 경우는 1이 됩니다. 이러한 경우 현재 가중치가 0이되는 정점들을 먼저 해결하고 그 뒤 1인 가중치의 문제를 해결해주면 됩니다. 따라서 큐를 두개 만들어 가중치가 0인 정점들과 1인 정점들을 따로 넣어줍니다. 그리고 0인 정점들을 모두 찾아 해결해줍니다. 그러면 현재 가중치가 0인 정점들은 없게 됩니다. 이 때 1로 모아둔 정점들을 해결해주고 2인 정점들은 따로 큐를 만들어 모아줍니다. 이런 식으로 1씩 가중치를 늘려가며 모두 해결하면 가중치가 0과 1인 정점들도 해결이 가능합니다. 이해를 돕기위해 말을 덧붙이면 0과 1인 정점이라고 하기 보다 가중치가 +0과 +1인 정점들을 따로 모아준다고 보면 좋을 것 같습니다.
다른 해결방안으로는 덱을 사용하는 방법이 있습니다. 덱은 앞과 뒤로 삽입 혹은 삭제가 가능한 자료구조입니다. 앞으로는 0 뒤로는 가중치가 1인 정점들을 넣어주고 해결해주면 됩니다. 저는 덱은 잘 사용하지않고 큐를 두개써서 해결합니다.
BFS로 모든 정점들에 대하여 확인하면 최종적으로 최소비용으로 목적지에 갈 수 있는 비용이 나옵니다.
가중치가 0이기 때문에 최소비용문제로 해결할 수 있었던 케이스입니다.
구현코드
package backjoon_1261;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] miro = new int[n][m];
for(int i =0; i < n; i++){
String line = sc.next();
for(int j = 0; j < m; j++){
miro[i][j] = line.charAt(j)-'0';
}
}
int[][] check = new int[n][m];
Queue<Integer> queue = new LinkedList<>();
Queue<Integer> nextQueue = new LinkedList<>();
queue.add(0);
queue.add(0);
check[0][0] = 1;
while (!queue.isEmpty()){
bfs(queue,nextQueue,miro,check);
if(queue.isEmpty()){
queue = nextQueue;
nextQueue = new LinkedList<>();
}
}
System.out.println(check[n-1][m-1] - 1);
}
public static void bfs(Queue<Integer> queue, Queue<Integer> nextQueue, int[][] miro,int [][] check){
int[] dx = {-1,0,1,0};
int[] dy = {0,1,0,-1};
int x = queue.remove();
int y = queue.remove();
for(int i = 0; i < dx.length; i++){
if(x+dx[i] >= 0 && x+dx[i] < miro.length && y+dy[i] >= 0 && y+dy[i] < miro[0].length && check[x+dx[i]][y+dy[i]] == 0){
if(miro[x+dx[i]][y+dy[i]] == 0){
queue.add(x+dx[i]);
queue.add(y+dy[i]);
check[x+dx[i]][y+dy[i]] = check[x][y];
}
else{
nextQueue.add(x+dx[i]);
nextQueue.add(y+dy[i]);
check[x+dx[i]][y+dy[i]] = check[x][y]+1;
}
}
}
}
}
시간복잡도
$O(V+E)$