문제 링크
알고리즘: BFS
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
풀이
벽을 k개 부실 수 있다. 그러면 방문 처리를 벽을 부신 횟수마다 다르게 해줘야 하는데 3차원 배열을 이용하면 간단하게 해결된다. 하지만 이 방법은 메모리 초과 및 시간 초과가 나올 확률이 크다고 생각했다. 그래서 3차원 배열이 아닌 2차원 배열을 이용했다. 일단 2차원 배열에 K+1로 전부 채워준다. K+1로 채워준 이유는 K개까지는 벽을 부수는 게 허용되기 때문이다. 그리고 다음 탐색을 할 때 조건을 주는데 벽을 더 적게 부수고 온 데이터만 다음 탐색을 허용시킨다. 그 이유는 벽을 부신 횟수가 같거나 큰 경우의 데이터가 뒤늦게 도착한 경우는 절대로 답이 될 수 없기 때문이다. 이렇게 구현하더라도 Queue를 직접 구현하지 않으면 답을 제한 내에 통과할 수 없다. Queue를 아래 코드처럼 구현해서 사용하는 것을 적극 추천한다.
소스코드 Java
import java.io.*;
import java.util.*;
class Node{
int x,y,z,c;
Node(int x, int y, int z, int c) {
this.x = x;
this.y = y;
this.z = z;
this.c = c;
}
}
public class Main {
static final int wx[] = {0,0,-1,1};
static final int wy[] = {-1,1,0,0};
static int map[][];
static int visited_min[][];
static int N, M, K;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited_min = new int[N][M];
for(int i=0; i<N; i++) {
String s = br.readLine();
Arrays.fill(visited_min[i], K+1);
for(int j=0; j<M; j++) {
map[i][j] = s.charAt(j) - '0';
}
}
System.out.println(BFS());
}
static int BFS() {
Queue<Node> que = new LinkedList<>();
que.add(new Node(0,0,0,1));
while(!que.isEmpty()) {
Node v = que.poll();
if(v.x == M-1 && v.y == N-1) {
return v.c;
}
for(int i = 0; i < 4; i++) {
int nx = v.x + wx[i];
int ny = v.y + wy[i];
if((nx>=0 && nx<=M-1) && (ny>=0 && ny<=N-1)) {
if(map[ny][nx] == 0) {
if(visited_min[ny][nx] > v.z) {
visited_min[ny][nx] = v.z;
que.add(new Node(nx, ny, v.z, v.c+1));
}
} else {
//벽을 만났을때
if(visited_min[ny][nx] > v.z+1) {
visited_min[ny][nx] = v.z+1;
que.add(new Node(nx, ny, v.z+1, v.c+1));
}
}
}
}
}
return -1;
}
}소스코드 JS
class Node{
constructor(x,y,z,c) {
this.x = x;
this.y = y;
this.z = z;
this.c = c;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
length() {
return this.size;
}
push(x,y,z,c) {
let node = new Node(x,y,z,c);
if(this.size === 0) {
this.front = node;
} else {
this.rear.next = node;
}
this.rear = node;
this.size++
}
pop_left() {
let value = this.front;
if(this.size === 0) {
this.front = null;
this.rear = null;
} else {
this.front = this.front.next;
}
this.size--;
return value;
}
}
const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let[N,M,K] = inputData[0].trim().split(' ').map(Number);
let map = Array.from(Array(N), () => Array(M));
let visited_min = Array.from(Array(N), () => Array(M).fill(K+1));
for(let i=1; i<inputData.length; i++) {
let input = inputData[i].trim().split('').map(Number);
for(let j=0; j<input.length; j++) {
map[i-1][j] = input[j];
}
}
console.log(BFS());
function BFS() {
let que = new Queue();
que.push(0, 0, 0, 1); //x,y,벽 부신 개수, count
let wx = [0, 0, -1, 1];
let wy = [-1, 1, 0, 0];
while(que.length()) {
let v = que.pop_left();
if((v.x===M-1) && (v.y===N-1)) {
return v.c;
}
for(let i=0; i<4; i++) {
let nx = v.x + wx[i];
let ny = v.y + wy[i];
if((nx>=0 && nx<=M-1) && (ny>=0 && ny<=N-1)) {
if(map[ny][nx] === 0) {
if(visited_min[ny][nx] > v.z) {
visited_min[ny][nx] = v.z;
que.push(nx,ny,v.z,v.c+1);
}
} else {
//벽을 만났을때
if(visited_min[ny][nx] > v.z+1) {
visited_min[ny][nx] = v.z+1;
que.push(nx,ny,v.z+1,v.c+1);
}
}
}
}
}
return -1;
}