[baekjoon] 2583 영역 구하기 (Javascript,c++)

2583번: 영역 구하기 (acmicpc.net)

2583번: 영역 구하기

---

접근 : bfs

 

1. 초기 m,n 값을 받고 k값을 받은 후 graph에 정렬시 주의

2. m값이 위쪽부터 0이 아닌, 아래부터 0으로 생각해서 좌표 처리 후 bfs

 

---

Javascript

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

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 [m, n, k] = input
  .shift()
  .split(" ")
  .map((v) => +v);

let graph = new Array(m).fill().map(() => new Array(n).fill(0));
let vis = new Array(m).fill().map(() => new Array(n).fill(0));

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

function bfs(x, y) {
  let q = new Queue();
  vis[x][y] = 1;
  q.push([x, y]);
  let cnt = 1;
  while (q.size() !== 0) {
    let [curX, curY] = q.pop();
    for (let dir = 0; dir < 4; dir++) {
      let nx = curX + dx[dir];
      let ny = curY + dy[dir];
      if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
      if (graph[nx][ny] === 1 || vis[nx][ny] === 1) continue;
      vis[nx][ny] = 1;
      q.push([nx, ny]);
      cnt++;
    }
  }
  return cnt;
}
function solution() {
  //graph
  for (let i = 0; i < k; i++) {
    let [y1, x1, y2, x2] = input
      .shift()
      .split(" ")
      .map((v) => +v);
    x1 = m - x1;
    x2 = m - x2;

    for (let i = x2; i < x1; i++) {
      for (let j = y1; j < y2; j++) {
        graph[i][j] = 1;
      }
    }
  }
  let count = 0;
  let answer = [];
  //check
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (graph[i][j] === 0 && vis[i][j] === 0) {
        count++;
        answer.push(bfs(i, j));
      }
    }
  }
  answer.sort((a, b) => a - b);

  console.log(count);
  console.log(answer.join(" "));
}

solution();

---

C++

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

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

int m,n,k;
int graph[101][101] = {0,};
int vis[101][101]={0,};

queue<pair<int,int>> Q;
int bfs(int x,int y){
  Q.push({x,y});
  vis[x][y] =1;
  int cnt = 1;
  while(!Q.empty()){
    auto cur = Q.front();
    Q.pop();
    for(int dir = 0; dir<4;dir++){
      int nx = cur.first + dx[dir];
      int ny = cur.second + dy[dir];
      if(nx<0||ny<0||nx>=m||ny>=n) continue;
      if(graph[nx][ny]==1||vis[nx][ny]==1) continue;
      cnt++;
      vis[nx][ny]=1;
      Q.push({nx,ny});
    }
  }
  return cnt;
}

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

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

    cin>>m>>n>>k;

    for(int i=0;i<k;i++){
      int x1,x2,y1,y2;
      cin>>y1>>x1>>y2>>x2;
      x1=m-x1;
      x2=m-x2;

      for (int x = x2; x < x1; x++) {
        for (int y = y1; y < y2; y++) {
          graph[x][y] = 1;
        }
      }
    }
    int count=0;
    vector<int> answer;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
      if (graph[i][j]== 0 && vis[i][j] == 0) {
        count++;
        answer.push_back(bfs(i, j));
      }
    }
  }

  sort(answer.begin(),answer.end());

  cout<<count<<"\n";
  for(auto a : answer){
    cout<<a<<" ";
  }

  

}