[baekjoon] 2468 안전영역 (Javascript, c++)

2468번: 안전 영역 (acmicpc.net)

2468번: 안전 영역

---

접근 : BFS

 

Javascript

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

let n = +input.shift();
let graph = [];
let vis = new Array(n).fill().map(() => new Array(n).fill(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;
  }
}

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

function BFS(x, y, cgraph, cvis, i) {
  cvis[x][y] = 1;
  let q = new Queue();
  q.push([x, y]);
  while (q.size() !== 0) {
    let [X, Y] = q.pop();
    for (let dir = 0; dir < 4; dir++) {
      let nx = X + dx[dir];
      let ny = Y + dy[dir];
      if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
      if (cgraph[nx][ny] <= i || cvis[nx][ny] === 1) continue;
      cvis[nx][ny] = 1;
      q.push([nx, ny]);
    }
  }
}

function solution() {
  for (let i = 0; i < n; i++) {
    graph.push(
      input
        .shift()
        .split(" ")
        .map((v) => +v)
    );
  }

  let answer = 1;

  for (let i = 1; i <= 100; i++) {
    let copyGraph = graph.map((v) => [...v]);
    let copyVis = vis.map((v) => [...v]);
    let cnt = 0;
    for (let a = 0; a < n; a++) {
      for (let b = 0; b < n; b++) {
        if (copyGraph[a][b] > i && copyVis[a][b] === 0) {
          cnt++;
          BFS(a, b, copyGraph, copyVis, i);
        }
      }
    }

    answer = Math.max(answer, cnt);
  }

  console.log(answer);
}

solution();

---

C++

#include <bits/stdc++.h>
using namespace std;
int n, maxcnt, maxlimit;
int graph[101][101];
bool vis[101][101];
queue<pair<int,int>> Q;

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

void bfs(int i, int j, int limit){
  queue<pair<int,int>> q;
  vis[i][j] = 1; 
  q.push({i, j}); 
  while(!q.empty()){
    auto cur = q.front(); q.pop();

    for(int i = 0; i < 4; i++){
      int nx = cur.first + dx[i];
      int ny = cur.second + dy[i];

      if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 
      if(vis[nx][ny] == 0 && graph[nx][ny] > limit){  
        vis[nx][ny] = 1;  
        q.push({nx, ny}); 
      }
    }
  }
}

int main(void) {
  freopen("input.txt", "r", stdin);
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> graph[i][j];
      maxlimit = max(graph[i][j], maxlimit);
    }
  }

  for(int limit = 0; limit <= maxlimit; limit++) {
    for(int i = 0; i < n; i++)
      fill(vis[i], vis[i]+n, 0);
    
    int cnt = 0;
    for(int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (graph[i][j] > limit && vis[i][j] == 0) {
          bfs(i, j, limit);
          cnt++;
        }
      }
    }
    maxcnt = max(cnt, maxcnt);
  }
  cout << maxcnt;
}