[백준/G5] 7576 토마토

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

python

arr에 그대로 변화를 주며 쌓아가는것이 중요
(동시에 arr에 변화가 일어나는것에 주의해야함)

172684kb 392ms PyPy3

import sys
from collections import deque

input = sys.stdin.readline

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


def bfs(tom):
    q = deque(tom)

    while q:
        x, y = q.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if not (0 <= nx < N and 0 <= ny < M):
                continue

            # 익지 않은 토마토라면
            if arr[nx][ny] == 0:
                q.append((nx, ny))
                arr[nx][ny] = arr[x][y] + 1


M, N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = 0

tomato = []
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            tomato.append((i, j))

bfs(tomato)
ans = max(max(row) for row in arr)

# 안익은 토마토가 남아있는지 확인
for row in arr:
    if 0 in row:
        print(-1)
        sys.exit(0)

print(ans - 1)

JS

뭘해도 시간초과가 나길래 온갖 방법을 다 해봤는데
결국 JS에는 기본적으로 Queue가 제공되지 않기 때문에 shift의 효율성이 문제였다

그래서
1. Queue를 직접 만들거나
2. shift를 대체하여 인덱스로 옮겨가며 만들기가 있었는데
2번으로 구현

157612kb	792ms	node.js

const fs = require("fs");

const filePath = process.platform === "linux" ? "/dev/stdin" : "./7576.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const dx = [1, 0, -1, 0];
const dy = [0, -1, 0, 1];

function bfs(tom) {
  const q = [...tom];
	let head = 0
  while (q.length > head) {
    const [x, y] = q[head];

    for (let d = 0; d < 4; d++) {
      const nx = x + dx[d];
      const ny = y + dy[d];

      if (!(0 <= nx && nx < N && 0 <= ny && ny < M)) {
        continue;
      }

      // 안익은 토마토일 때 1씩 더해감
      if (arr[nx][ny] === 0) {
        q.push([nx, ny]);
        arr[nx][ny] = arr[x][y] + 1;
      }
    }
		head++
  }
}

const [M, N] = input[0].split(" ").map(Number);
const arr = input.slice(1).map((line) => line.split(" ").map(Number));

let ans = 0;

const tomato = [];
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (arr[i][j] === 1) {
      tomato.push([i, j]);
    }
  }
}

bfs(tomato);


// 안익은 토마토가 남아있는지 확인
check = true
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    // 익지 않은 토마토가 있음
    if (arr[i][j] === 0) {

			check = false
			break
    }
  }
}
if (check) {
  ans = Math.max(...arr.map((row) => Math.max(...row)))-1;
} else {
	ans = -1
}
console.log(ans)

queue를 직접 js로 정의해서 써먹는 방법도...공부해봐야할듯
java도 ArrayDeque나 LinkedList로 큐가 쉽게 만들어지는데ㅠ

+하단은 두 자료구조의 차이
https://velog.io/@newdana01/Java-큐-구현시-ArrayDeque와-LinkedList-성능-차이-Deque-Queue-인터페이스