[구름톤 챌린지] 연결 요소 제거하기 (JS)

hhkim·2023년 9월 8일
0

Algorithm - JavaScript

목록 보기
127/188
post-thumbnail

풀이 과정

  1. Q번 반복
  2. 배열의 각 요소에 대해 반복
  3. 배열과 같은 visited 배열 생성
  4. 현재 연결 요소의 좌표들을 담을 배열 생성
  5. BFS 탐색
  6. 4번 배열 길이가 K 이상이면 원본 배열에 있는 방문 값들을 .으로 바꾸기

코드

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
let N, K, Q;
rl.on('line', (line) => {
  input.push(line.trim());
  [N, K, Q] = input[0].split(' ').map(Number);
  if (input.length === N + Q + 1) {
    rl.close();
  }
});

// 오른 아래 왼 위
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

rl.on('close', () => {
  const arr = [];
  const selected = [];
  for (let i = 1; i <= N; ++i) {
    arr.push(input[i].split(''));
  }
  for (let i = N + 1; i <= N + Q; ++i) {
    let [r, c, d] = input[i].split(' ');
    [r, c] = [r, c].map((e) => Number(e) - 1);
    selected.push([r, c, d]);
  }

  for (const [r, c, d] of selected) {
    const visited = Array(N)
      .fill(null)
      .map((_) => Array(N).fill(false));
    arr[r][c] = d;
    for (let i = 0; i < N; ++i) {
      for (let j = 0; j < N; ++j) {
        if (arr[i][j] === '.') continue;
        const connected = [[i, j]];
        const q = [[i, j]];
        visited[i][j] = true;
        while (q.length) {
          const [y, x] = q.shift();
          for (let k = 0; k < 4; ++k) {
            const ny = y + dy[k];
            const nx = x + dx[k];
            if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
            if (arr[ny][nx] !== arr[y][x]) continue;
            if (visited[ny][nx]) continue;
            q.push([ny, nx]);
            connected.push([ny, nx]);
            visited[ny][nx] = true;
          }
        }
        if (connected.length < K) continue;
        for (const [y, x] of connected) {
          arr[y][x] = '.';
        }
      }
    }
  }

  for (const line of arr) {
    console.log(line.join(''));
  }
  process.exit();
});

🦾

마지막 문제를 풀고 끝낼 수 있어서 너무 뿌듯하다. 챌린지 이전에는 이런 문제 보면 겁부터 먹었을 것 같은데 이제 도전하는 용기가 생겼다. 구름톤 챌린지를 만들어주신 분들께 무한 감사를 올려봅니다 🙇 이렇게 한 달 동안의 챌린지 끝!

0개의 댓글