접근 : 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";
}
'코딩테스트(알고리즘) > baekjoon' 카테고리의 다른 글
[baekjoon] 10828 스택 (Javascript) (0) | 2022.06.30 |
---|---|
[baekjoon] 1697 숨바꼭질 (Javascript,C++) (0) | 2022.06.29 |
[baekjoon] 7576 토마토 (C++,Javascript) (0) | 2022.06.29 |
[baekjoon] 2178 미로탐색 (Javascript,C++) (0) | 2022.06.28 |
[baekjoon] 1463 1로만들기 (Javascript) (0) | 2022.06.26 |