[ALGO] - 백준 구현 문제(javascript)

211024

배열 돌리기 1

const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');

const [N, M, R] = input[0].split(' ').map(Number);
let arr = [];
for (let i = 1; i <= N; i++) arr.push(input[i].split(' ').map(Number));

for (let i = 0; i < R; i++) {
  for (let idx = 0; idx < Math.min(N, M) / 2; idx++) {
    let prev = arr[idx][idx];

    for (let k = 1 + idx; k < N - idx; k++) {
      const cur = arr[k][idx];
      arr[k][idx] = prev;
      prev = cur;
    }

    for (let k = 1 + idx; k < M - idx; k++) {
      const cur = arr[N - 1 - idx][k];
      arr[N - 1 - idx][k] = prev;
      prev = cur;
    }

    for (let k = N - 2 - idx; k >= idx; k--) {
      const cur = arr[k][M - 1 - idx];
      arr[k][M - 1 - idx] = prev;
      prev = cur;
    }

    for (let k = M - 2 - idx; k >= idx; k--) {
      const cur = arr[idx][k];
      arr[idx][k] = prev;
      prev = cur;
    }
  }
}

arr.map((x) => console.log(x.join(' ')));

• dfs

const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');

const [N, M, R] = input[0].split(' ').map(Number);
let arr = [];
for (let i = 1; i <= N; i++) arr.push(input[i].split(' ').map(Number));

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

for (let i = 0; i < R; i++) {
  for (let idx = 0; idx < Math.min(N, M) / 2; idx++) {
    let x = idx,
      y = idx;
    let prev = arr[x][y];

    // dfs
    let k = 0;
    while (k < 4) {
      const nx = x + dx[k];
      const ny = y + dy[k];

      if (idx > nx || nx >= N - idx || idx > ny || ny >= M - idx) k++;
      else {
        const cur = arr[nx][ny];
        arr[nx][ny] = prev;
        prev = cur;
        (x = nx), (y = ny);
      }
    }
    arr[idx + 1][idx] = prev;
  }
}

arr.map((x) => console.log(x.join(' ')));

reference

• 백준 16926 배열 돌리기 1
• 백준 알고리즘 백준 16926번 배열돌리기1 자바Java

인구 이동

const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');

const [N, L, R] = input[0].split(' ').map(Number);
const arr = [];
for (let i = 1; i <= N; i++) arr.push(input[i].split(' ').map(Number));

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

function DFS(i, j, dis) {
  let stack = [[i, j]];
  let sum = arr[i][j];
  dis[i][j] = true;

  let idx = 0;
  while (stack.length > idx) {
    const [x, y] = stack[idx];

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

      const diff = Math.abs(arr[x][y] - arr[nx][ny]);
      if (L <= diff && diff <= R && !dis[nx][ny]) {
        stack.push([nx, ny]);
        sum += arr[nx][ny];
        dis[nx][ny] = true;
      }
    }

    idx += 1;
  }
  return [stack, sum];
}

(function solution() {
  let cnt = 0;

  while (true) {
    let flag = false;
    let dis = Array.from(Array(N), () => new Array(N).fill(false));

    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        if (!dis[i][j]) {
          const [union, sum] = DFS(i, j, dis);

          if (union.length > 1) {
            flag = true;
            move(union, sum);
          } else false; // add
        }
      }
    }

    if (!flag) break;
    cnt += 1;
  }
  console.log(cnt);
})();

function move(union, sum) {
  const people = parseInt(sum / union.length);
  union.map(([x, y]) => (arr[x][y] = people));
}

달팽이

const [N, num] = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n').map(Number);

let arr = Array.from(Array(N), () => new Array(N).fill(0));

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

let ans_coord = [];
let prev = N * N;
for (let i = 0; i < parseInt(N / 2); i++) {
  let x = i, y = i;

  let k = 0;
  while (k < 4) {
    const nx = x + dx[k];
    const ny = y + dy[k];

    if (i > nx || nx >= N - i || i > ny || ny >= N - i) k++;
    else {
      arr[x][y] = prev;
      if (prev === num) ans_coord.push(x + 1, y + 1);
      prev -= 1;
      (x = nx), (y = ny);
    }
  }
}

if (N % 2 !== 0) arr[parseInt(N / 2)][parseInt(N / 2)] = 1;

arr.map((x) => console.log(x.join(' ')));
console.log(
  num === 1
    ? `${parseInt(N / 2) + 1} ${parseInt(N / 2) + 1}`
    : ans_coord.join(' ')
);