[baekjoon] 1012 유기농 배추 (C++,Javascript)

1012번: 유기농 배추 (acmicpc.net)

1012번: 유기농 배추

---

접근 : BFS

 

문제는 간단하게 풀었으나 C++ 풀이 중 WithoutReturning 에러가 계속 발생해서 고생했다.

결국 문제는 bfs 함수에서 return값이 없어서 발생한 문제로 확인.

c++에 익숙하지 않아서 발생하는 문제라고 생각한다.

 

---

Javascript

/**
 * 제출용. 아래 로컬용을 지우고 제출하자.
 */
//  let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
/**
 * 로컬용, 예제.txt를 생성해서 예제를 복붙하자.
 */
let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());

let t = +input.shift();
let n, m;

let graph;
let vis;

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) {
  vis[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 >= m) continue;
      if (graph[nx][ny] !== 1 || vis[nx][ny] === 1) continue;
      vis[nx][ny] = 1;
      q.push([nx, ny]);
    }
  }
}

function solution() {
  while (t--) {
    graph = new Array(51).fill().map(() => new Array(51).fill(0));
    vis = new Array(51).fill().map(() => new Array(51).fill(0));
    let cnt = 0;
    let [m, n, k] = input
      .shift()
      .split(" ")
      .map((v) => +v);

    for (let i = 0; i < k; i++) {
      let [x, y] = input
        .shift()
        .split(" ")
        .map((v) => +v);
      graph[y][x] = 1;
    }

    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if (graph[i][j] === 1 && vis[i][j] === 0) {
          cnt++;
          BFS(i, j);
        }
      }
    }

    console.log(cnt);
  }
}

solution();

---

C++

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

int m,n,k;
int graph[51][51];
bool visited[51][51];
queue<pair<int,int>> Q;

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

int BFS(int x,int y){
  visited[x][y] = true;
  Q.push({x,y});
  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||nx>=n||ny<0||ny>=m) continue;
       if(graph[nx][ny]!=1||visited[nx][ny]) continue;
       visited[nx][ny]=1;
       Q.push({nx,ny});
    }
  }
  return 0;
}


int main()
{

    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  int t;
  cin>>t;
  
  while(t--){
    fill(&visited[0][0],&visited[0][0]+51*51,0);
    fill(&graph[0][0],&graph[0][0]+51*51,0);

    int cnt = 0;
    cin>>m>>n>>k;
    int x,y;
    for(int i=0;i<k;i++){
      cin>>x>>y;
      graph[y][x]= 1;
    }

    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(graph[i][j]==1&&!visited[i][j]){
          cnt++;
          BFS(i,j);
        }
      }
    }

    cout<<cnt<<"\n";

  }
  return 0;

}