[baekjoon] 2178 미로탐색 (Javascript,C++)

2178번: 미로 탐색 (acmicpc.net)

2178번: 미로 탐색

---

접근 : 최단경로! bfs

 

Javascript

let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());
function solution(input) {
  //input
  let [n, m] = input
    .shift()
    .split(" ")
    .map((v) => +v);
  let graph = [];
  for (let i = 0; i < n; i++) {
    graph.push(input.shift().split(""));
  }

  let visit = new Array(n).fill().map(() => new Array(m).fill(-1));

  let answer = BFS(0, 0, graph, visit, n, m);

  console.log(answer);
}

function BFS(x, y, graph, visit, n, m) {
  let dx = [0, 1, 0, -1];
  let dy = [1, 0, -1, 0];
  let queue = [];
  visit[x][y] = 0;
  queue.push([x, y]);
  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 (visit[nx][ny] >= 0 || graph[nx][ny] === "0") continue;
      visit[nx][ny] = visit[curX][curY] + 1;
      queue.push([nx, ny]);
    }
  }
  console.log(visit);

  return visit[n - 1][m - 1] + 1;
}

solution(input);

---

c++

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

#define X first
#define Y second

string graph[102];
int vis[102][102];
int n,m;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int BFS(int x,int y){
  queue<pair<int,int>> Q;
  vis[x][y] = 0;
  Q.push({x,y});

  while(!Q.empty()){
    pair<int,int> cur = Q.front();
    Q.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(vis[nx][ny]>=0||graph[nx][ny]!='1') continue;
      vis[nx][ny] = vis[cur.X][cur.Y]+1;
      Q.push({nx,ny});
    }
  }
    return vis[n-1][m-1]+1;
}

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++){
      cin>>graph[i];
    }

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

    int answer = BFS(0,0);

  cout<<answer<<"\n";

}