백준 7576 < 토마토 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

📍알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

 

📍문제 풀이

- 그래프를 순회하며 모든 정점을 방문하는 최소 depth를 출력, 모두 방문하지 못하면 -1, 이미 모두 방문되어 있으면  0을 출력

- depth를 늘려가며 모두 방문하기 때문에, BFS를 사용

- BFS가 수행되고 나면, 1인 좌표에 인접한 좌표는 +1 해서 2가 되고, 2인 좌표에 인접한 좌표는 +1 해서 3이 되는 방식

 

📍의사 코드

- 반복 BFS를 위해 큐를 구현 (이중 연결 리스트)

 

- bfs 함수 구현

인수 : 토마토 좌표맵, 큐 (토마토가 있는 좌표 리스트)

큐에 데이터가 존재하는 동안 반복

-> 좌표 하나 꺼냄 (dequeue)

-> 상하좌우가 빈 자리이면 큐에 넣고 좌표맵에 현재 값(1) +1을 할당

 

- 토마토 좌표맵 2차원 리스트를 순회하며 큐에 데이터 입력

- BFS 실행

- 좌표맵이 모두 방문되면, 중첩 반복문을 통해 좌표맵의 상태에 따라 값 출력

 

📍코드 (JavaScript)

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const [column, row] = input.shift().split(" ").map(Number);
const map = input.map((r) => r.split(" ").map(Number));

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  enqueue(val) {
    const newNode = new Node(val);
    if (this.size === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }
  dequeue() {
    if (this.size === 0) return null;
    const removedNode = this.first;
    if (this.first === this.last) {
      this.first = null;
    } else {
      this.first = this.first.next;
    }
    this.size--;
    return removedNode;
  }
}

const queue = new Queue();

function bfs(arr, data) {
  while (data.size) {
    const currentVertex = data.dequeue().val;
    const Y = currentVertex[0];
    const X = currentVertex[1];
    const day = arr[Y][X];

    if (Y - 1 >= 0 && arr[Y - 1][X] === 0) {
      data.enqueue([Y - 1, X]);
      arr[Y - 1][X] = day + 1;
    }
    if (Y + 1 < row && arr[Y + 1][X] === 0) {
      data.enqueue([Y + 1, X]);
      arr[Y + 1][X] = day + 1;
    }
    if (X - 1 >= 0 && arr[Y][X - 1] === 0) {
      data.enqueue([Y, X - 1]);
      arr[Y][X - 1] = day + 1;
    }
    if (X + 1 < column && arr[Y][X + 1] === 0) {
      data.enqueue([Y, X + 1]);
      arr[Y][X + 1] = day + 1;
    }
  }
}

for (let i = 0; i < row; i++) {
  for (let j = 0; j < column; j++) {
    if (map[i][j] === 1) queue.enqueue([i, j]);
  }
}

bfs(map, queue);

let max = 0;
let printed = false;
outer: for (let i = 0; i < row; i++) {
  for (let j = 0; j < column; j++) {
    if (map[i][j] === 0) {
      console.log(-1);
      printed = true;
      break outer;
    }
    if (map[i][j] > max) max = map[i][j];
  }
}
if (!printed) max > 1 ? console.log(max - 1) : console.log(0);

 

📍리뷰

- label을 외부 반복문에 부착하여, 내부 반복문에서 한번에 break 가능