백준_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)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

예제 입력 1

3 3
011
111
110

예제 출력 1

3

풀이 및 해설

출력값: 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 부숴야 하는 벽의 최솟값

• 빈방(0)은 자유롭게 다닐 수 있지만, 벽(1)은 부수지 않으면 이동할 수 없음
• 상하좌우로만 이동 가능
• (1, 1)과 (N, M)은 항상 뚫려있음

백트래킹 풀이
1. 상하좌우로 이동했을 때

• 영역을 벗어나지 않고, 아직 방문하지 않은 공간인 경우 백트래킹 수행
• 빈 방인 경우 부수지 않고, 벽인 경우 부순 횟수 카운트 증가

2. (N, M)에 도달했을 때, 부순 횟수의 최솟값 갱신

▶︎ 시간초과 발생

시간복잡도 → $O(2^{NM})$

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [M, N] = input[0].split(' ').map(Number); // M: 가로, N: 세로
const maze = []; // 미로(0: 빈 방, 1: 벽)
for (let n = 1; n <= N; n++) maze.push(input[n].split('').map(Number));

const drdc = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
]; // 상하좌우 이동 방향

let result = Number.MAX_SAFE_INTEGER;
const visited = Array.from({ length: N }, () => new Array(M).fill(false));
const backtracking = (r, c, cnt) => {
  if (r === N - 1 && c === M - 1) {
    result = Math.min(result, cnt);
    return;
  }
  for (let [dr, dc] of drdc) {
    const [nr, nc] = [r + dr, c + dc];
    if (nr >= 0 && nr < N && nc >= 0 && nc < M && !visited[nr][nc]) {
      visited[nr][nc] = true;
      backtracking(nr, nc, maze[nr][nc] === 1 ? cnt + 1 : cnt);
      visited[nr][nc] = false;
    }
  }
  return;
};

visited[0][0] = true;
backtracking(0, 0, 0);

console.log(result);

0-1 BFS로 풀이

0-1 BFS?
가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS 응용해서 푸는 방식

❓ 최단 경로를 구할 때 사용하는 다익스트라 알고리즘과 차이는?
: 다익스트라 알고리즘의 시간복잡도는 $O(ElogE)$ 혹은 $O(ElogV)$ 이지만, 0-1 BFS의 시간복잡도는 $O(V+E)$의 선형 시간 복잡도로 문제 해결 가능

0-1 BFS 동작 방식

덱(deque)이용

덱(Deque)
앞, 뒤로 데이터 추가, 삭제 가능 → 즉, 스택(Stack) + 큐(Queue)

1. 덱의 앞에서 현재 노드 꺼냄
2. 꺼낸 노드와 연결된 인접 노드 확인
3. 현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 갱신
4. 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 앞에 삽입, 1이면 덱의 뒤에 삽입
5. 더 이상 덱에서 꺼낼 노드가 없을 때까지 반복

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [M, N] = input[0].split(' ').map(Number); // M: 가로, N: 세로
const maze = []; // 미로(0: 빈 방, 1: 벽)
for (let n = 1; n <= N; n++) maze.push(input[n].split('').map(Number));

const drdc = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
]; // 상하좌우 이동 방향

const deque = [];
const visited = Array.from({ length: N }, () => new Array(M).fill(-1));

deque.push([0, 0, 0]);
visited[0][0] = 0;

while (deque.length) {
  const [curR, curC, cost] = deque.shift();
  for (const [dr, dc] of drdc) {
    const [nr, nc] = [curR + dr, curC + dc];
    if (nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] === -1) {
      if (maze[nr][nc] === 0) {
        visited[nr][nc] = cost;
        deque.unshift([nr, nc, cost]);
      } else {
        visited[nr][nc] = cost + 1;
        deque.push([nr, nc, cost + 1]);
      }
    }
  }
}

console.log(visited[N - 1][M - 1]);

Deque 클래스 구현

class Deque {
  constructor() {
    this.data = [];
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  // 뒤에서 삽입
  push = (item) => {
    this.data[this.tailIndex++] = item;
  };
  // 앞에서 삽입
  unshift = (item) => {
    this.data[--this.headIndex] = item;
  };
  // 앞에서 삭제
  shift = () => this.data[this.headIndex++];
  // 뒤에서 삭제
  pop = () => this.data[this.tailIndex--];
  // 길이 출력
  getLength = () => this.tailIndex - this.headIndex;
}