[baekjoon] 4179 불! (C++,Javascript)

4179번: 불! (acmicpc.net)

4179번: 불!

---

접근 : BFS

 

자바스크립트 시간초과를 극복하기 위해 큐를 구현하여 풀이 완료.

 

Javascript

let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());

let [n, m] = input
  .shift()
  .split(" ")
  .map((v) => +v);

let graph = [];
for (let i = 0; i < n; i++) {
  graph.push(input.shift().split(""));
}
let visit1 = Array.from(Array(n), () => new Array(m).fill(-1));
let visit2 = Array.from(Array(n), () => new Array(m).fill(-1));

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

class Queue {
  constructor() {
    this.arr = [];
    this.head = 0;
    this.tail = 0;
  }

  push(data) {
    this.arr[this.tail++] = data;
  }
  pop() {
    return this.arr[this.head++];
  }
  size() {
    return this.tail - this.head;
  }
}
function solution() {
  let q1 = new Queue();
  let q2 = new Queue();
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (graph[i][j] === "F") {
        q1.push([i, j]);
        visit1[i][j] = 0;
      }
      if (graph[i][j] === "J") {
        q2.push([i, j]);
        visit2[i][j] = 0;
      }
    }
  }

  //fire
  while (q1.size()) {
    let [x, y] = q1.pop();
    for (let dir = 0; dir < 4; dir++) {
      let nx = x + dx[dir];
      let ny = y + dy[dir];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (graph[nx][ny] === "#" || visit1[nx][ny] >= 0) continue;
      visit1[nx][ny] = visit1[x][y] + 1;
      q1.push([nx, ny]);
    }
  }

  //people
  while (q2.size()) {
    let [x, y] = q2.pop();
    for (let dir = 0; dir < 4; dir++) {
      let nx = x + dx[dir];
      let ny = y + dy[dir];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
        console.log(visit2[x][y] + 1);
        return;
      }
      if (graph[nx][ny] === "#" || visit2[nx][ny] >= 0) continue;
      if (visit1[nx][ny] !== -1 && visit1[nx][ny] <= visit2[x][y] + 1) continue;
      visit2[nx][ny] = visit2[x][y] + 1;
      q2.push([nx, ny]);
    }
  }

  console.log("IMPOSSIBLE");
}

solution();

---

C++

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

#define X first
#define Y second

int n,m;
string graph[1002];
int visited_F[1002][1002];
int visited_J[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>>n>>m;
    for(int i = 0; i < n; i++){
    fill(visited_F[i], visited_F[i]+m, -1);
    fill(visited_J[i], visited_J[i]+m, -1);    
  }

    queue<pair<int,int>> q_F;
    queue<pair<int,int>> q_J;
    for(int i=0;i<n;i++){
      cin>>graph[i];
      for(int j=0;j<m;j++){
        if(graph[i][j]=='F') {
          q_F.push({i,j});
          visited_F[i][j]=0;
        }
        if(graph[i][j]=='J') {
          q_J.push({i,j});
          visited_J[i][j]=0;
      }
    }
    }


    //불 전파
    while(!q_F.empty()){
      auto cur = q_F.front();
      q_F.pop();
      for(int dir=0;dir<4;dir++){
        int nx = cur.X+dx[dir];
        int ny = cur.Y+dy[dir];
        if(nx<0||nx>=n||ny<0||ny>=m) continue;
        if(graph[nx][ny]=='#'||visited_F[nx][ny]>=0) continue;
        visited_F[nx][ny]=visited_F[cur.X][cur.Y]+1;
        q_F.push({nx,ny});
      }
    }

    //지훈 탈출
    while(!q_J.empty()){
      auto cur = q_J.front();
      q_J.pop();
      for(int dir=0;dir<4;dir++){
        int nx = cur.X+dx[dir];
        int ny = cur.Y+dy[dir];
        if(nx<0||nx>=n||ny<0||ny>=m) {
          cout<<visited_J[cur.X][cur.Y]+1<<"\n";
          return 0;
        }
        if(graph[nx][ny]=='#'||visited_J[nx][ny]>=0) continue;
        if(visited_F[nx][ny]!=-1 && visited_F[nx][ny]<=visited_J[cur.X][cur.Y]+1) continue;
        visited_J[nx][ny]=visited_J[cur.X][cur.Y]+1;
        q_J.push({nx,ny});
      }
    }
      cout<<"IMPOSSIBLE"<<"\n";


}