BFS 문제풀이(5)

9. 치즈(2638)

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

https://upload.acmicpc.net/a00b876a-86dc-4a82-a030-603a9b1593cc/-/preview/

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

작성한 코드

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}

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

let [n, m] = input[0].split(" ").map(Number); // 모눈종이 크기
let graph = []; // 모눈종이 위 치즈가 있는 부분
for (let i = 0; i < n; i++) {
  graph[i] = input[i + 1].split(" ").map(Number);
}

// 상, 하, 좌, 우 방향 정보
let dx = [0, 0, -1, 1];
let dy = [1, -1, 0, 0];

function bfs() {
  let visited = []; // 방문 처리 배열
  for (let i = 0; i < n; i++) visited.push(new Array(m).fill(false));
  visited[0][0] = true; // 제일 왼쪽 위에서 출발
  let queue = new Queue();
  queue.enqueue([0, 0]);
  while (queue.getLength() != 0) {
    let [x, y] = queue.dequeue();
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      // 맵을 벗어나는 경우 무시
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (!visited[nx][ny]) {
        if (graph[nx][ny] >= 1) graph[nx][ny] += 1; // 카운트 증가
        else {
          queue.enqueue([nx, ny]);
          visited[nx][ny] = true;
        }
      }
    }
  }
}

function melt() {
  let finish = true; // 더 녹일 치즈가 없는지 여부
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      // 녹일 치즈라면
      if (graph[i][j] >= 3) {
        graph[i][j] = 0; // 녹이기
        finish = false;
      } else if (graph[i][j] == 2) graph[i][j] = 1; // 한 면만 닿은 경우 무시
    }
  }
  return finish;
}

let result = 0;
while (true) {
  bfs();
  if (melt()) {
    console.log(result); // 전부 녹았다면
    break;
  } else result += 1;
}

풀이

• BFS로 녹일 위치를 선택하고, 녹이는 과정을 반복 수행
  • BFS 파트

    1. (0,0) 위치에서 출발하여 BFS 진행

    2. 큐에서 하나의 원소 꺼낸 뒤에 상, 하, 좌, 우 위치 확인

       인접한 위치에 치즈가 있다면, 치즈가 있는 위치에 대하여 카운트

  • 녹이기 파트
    1. 카운트가 2 이상인 치즈 없애기

10. A ->B(16953)

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

내가 작성한 코드

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}

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

let [a, b] = input[0].split(" ").map(Number); // 정수 a, b

queue = new Queue(); // 큐 생성
queue.enqueue([a, 0]); // 시작점 [a, 연산 횟수=0]
let found = false;

while (queue.getLength() != 0) {
  queue.items.sort((a, b) => a - b);
  let [cur, cnt] = queue.dequeue();
  // A를 B로 변환되었을 때
  if (cur == b) {
    console.log(cnt + 1);
    found = true;
    break;
  }
  for (let oper of ["*", "+"]) {
    let next = cur;
    if (oper == "*") next *= 2; // 2 곱해주기
    if (oper == "+") next = Number(cur + "1"); // 맨 뒤에 1 더해주기
    queue.enqueue([next, cnt + 1]); // 연산횟수 늘려가며 queue에 넣기
    console.log(queue);
  }
}

// 만들 수 없는 경우
if (!found) {
  console.log(-1);
}

풀이

• BFS로 풀이
• *와 +일 때를 나누어서 수행
• 근데, queue가 오름차순이 아닌 넣는 순서에 따라 채워지기 때문에 값이 넘어버리거나 무한 루프가 발생하는 문제 있음 → 메모리 초과

작성한 코드

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}

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

let [a, b] = input[0].split(" ").map(Number); // 정수 a, b

queue = new Queue(); // 큐 생성
queue.enqueue([a, 0]); // 시작점 [a, 연산 횟수=0]
**let visited = new Set();**
let found = false;

while (queue.getLength() != 0) {
  let [cur, cnt] = queue.dequeue();
  **if (cur > 1e9) continue; // 범위를 벗어나는 경우**
  // A를 B로 변환되었을 때
  if (cur == b) {
    console.log(cnt + 1); // 최소 연산 횟수 + 1 출력
    found = true;
    break;
  }
  for (let oper of ["*", "+"]) {
    let next = cur;
    if (oper == "*") next *= 2; // 2 곱해주기
    if (oper == "+") next = Number(cur + "1"); // 맨 뒤에 1 더해주기
    **if (!visited.has(next)) {
      queue.enqueue([next, cnt + 1]); // 연산횟수 늘려가며 queue에 넣기
      visited.add(next);
    }**
  }
}

// 만들 수 없는 경우
if (!found) {
  console.log(-1);
}

풀이

• 사용할 수 있는 연산은 두 가지 종류 존재, “최소 연산 횟수” 구하기
  1. 2 곱하기
  2. 1을 오른쪽에 추가