백준 2667 단지 찾기 자바스크립트

문제

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

접근

 

풀이

// 공통 상단 코드
// 백준 제출시
// const address="/dev/stdin"

// VSC 테스트시
const address = "./input.txt";
const input = require("fs")
  .readFileSync(address)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split("").map(Number));

 

시도 1

결과: 실패

3,9,7,11

로 나옴 (답은 3,7,8,9)

seen(visited) 에 뭔가 중복이 있을 거라 생각하고 봤더니

이렇게 [1,2] 처럼 중복되어 있는 몇 배열들이 보인다.

Set()은 중복값이 안되는 걸로 알았는데 object 는 배열로 안치나보다. 

const solution = (input) => {
  const [N, ...graph] = input;
  let numOfComplex = 0;
  const houses = [];

  const filter = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
    else if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const seen = new Set();
    const queue = [[row, col]];
    seen.add([row, col]);
    let house = 0;
    console.log(`queue (${row}, ${col}): `, queue, "\n");

    while (queue.length) {
      const [x, y] = queue.shift();
      console.log("shifted: ", [x, y]);
      console.log("seen: ", seen);
      console.log("queue after loop: ", queue);
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y + 1],
        [x + 1, y],
        [x, y - 1],
      ];
      const validIdxPairs = idxPairs.filter((idx) => filter(idx));
      console.log("valid pairs:", validIdxPairs, "\n");
      for (const idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen.has([nx, ny])) {
          seen.add([nx, ny]);
          house++;
          queue.push([nx, ny]);
        }
      }
    }

    houses.push(house);
  };

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (graph[i][j] === 1) {
        numOfComplex++;
        bfs(i, j);
      }
    }
  }

  const answer = [numOfComplex, ...houses];
  return answer.join("\n");
};

console.log(solution(input));

시도2

수정사항:

- seen set -> arr

- house++ 새 라운드 시작할 때도 실행

- 인풋 받을 때 "\n" 까지만 받고 일일이 할당. 구조분해 x. 

 

결과: 실패

콘솔에는 답으로 뜨나 백준 제출시 "틀렸습니다"

const solution = (input) => {
  const N = +input.shift();
  const graph = input;
  let numOfComplex = 0;
  const houses = [];

  const filter = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
    else if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const seen = new Array(N).fill(0).map(() => new Array(N).fill(false));
    const queue = [[row, col]];
    let house = 0;
    seen[row][col] = true;
    house++;

    while (queue.length) {
      const [x, y] = queue.shift();
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y + 1],
        [x + 1, y],
        [x, y - 1],
      ];
      const validIdxPairs = idxPairs.filter((idx) => filter(idx));
      for (const idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen[nx][ny]) {
          seen[nx][ny] = true;
          house++;
          queue.push([nx, ny]);
        }
      }
    }

    houses.push(house);
  };

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (graph[i][j] === 1) {
        numOfComplex++;
        bfs(i, j);
      }
    }
  }

  const answer = [numOfComplex, ...houses];
  return answer.join("\n");
};

console.log(solution(input));