[baekjoon] 7576 토마토 (C++,Javascript)

7576번: 토마토 (acmicpc.net)

7576번: 토마토

---

접근 : BFS

 

Javascript는 시간초과 발생.

항상 백준에서는 queue shift를 직접 구현하지 않고 사용하면 시간초과가 많이 발생한다.

그런 경우를 위해 c++과 함께 준비하고 있다.

---

Javascript

/**
 * 제출용. 아래 로컬용을 지우고 제출하자.
 */
//  let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
/**
 * 로컬용, 예제.txt를 생성해서 예제를 복붙하자.
 */
let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());
let [m, n] = input
  .shift()
  .split(" ")
  .map((v) => +v);

let graph = [];
for (let i = 0; i < n; i++) {
  graph.push(input.shift().split(" "));
}
let visited = new Array(n).fill().map(() => new Array(m).fill(-2));

let dx = [0, 1, 0, -1];
let dy = [1, 0, -1, 0];
function solution() {
  let answer = 0;
  let check = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (graph[i][j] === "1") check.push([i, j]);
      if (graph[i][j] === "0") visited[i][j] = -1;
    }
  }

  if (check.length === 0) console.log(answer);
  else {
    let queue = [];
    check.forEach((v) => {
      visited[v[0]][v[1]] = 0;
      queue.push(v);
    });

    while (queue.length !== 0) {
      let [curX, curY] = queue.shift();
      for (let dir = 0; dir < 4; dir++) {
        let nx = curX + dx[dir];
        let ny = curY + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (graph[nx][ny] === "-1" || visited[nx][ny] >= 0) continue;
        visited[nx][ny] = visited[curX][curY] + 1;
        queue.push([nx, ny]);
      }
    }
    console.log(visited);

    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if (visited[i][j] === -1) {
          console.log(-1);
          return;
        } else {
          answer = Math.max(answer, graph[i][j]);
        }
      }
    }
    console.log(answer);
  }
}

solution();

---

C++

#include <bits/stdc++.h>
using namespace std;

int n,m,x,y,ret=0;
int graph[1002][1002];
int visited[1002][1002];

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int main()
{
  freopen("input.txt", "r", stdin); //제출 시 삭제

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>m>>n;

    for(int i=0;i<n;i++){
      fill(visited[i],visited[i]+m,-2);
    }

    queue<pair<int,int>> q;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        cin>>graph[i][j];
        if(graph[i][j]==1) {
          q.push({i,j}); 
          visited[i][j]=0;
          }
        if(graph[i][j]==0){
          visited[i][j]=-1;
        }
      }
    }

      while(!q.empty()){
        tie(x,y) = q.front();
        q.pop();
        for(int dir=0;dir<4;dir++){
          int nx = x+dx[dir];
          int ny = y+dy[dir];
          if(nx<0||nx>=n||ny<0||ny>=m) continue;
          if(graph[nx][ny]==-1||visited[nx][ny]>=0) continue;
          visited[nx][ny]=visited[x][y]+1;
          q.push({nx,ny});
        }
      }
      for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
          if(visited[i][j]==-1){
            cout<<-1;
            return 0;
          }
          ret = max(ret,visited[i][j]);
        }
      }
      cout<<ret;
    
}