[Algorithm] 백준 1074번 Z (Javascript, node.js)

백준 1074번!!

 

문제

크기가 2**N, 2**N 인 2차원 배열을 Z모양으로 탐색하려한다. 

 

N>1 인 경우, 이를 4등분한 후에 또 Z모양으로 방문한다.

예시는 아래와 같음!

N = 2

N = 3

 

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하자.

 

 

풀이

주키워드는 "사분면"과 "재귀함수" 이다. 

간단하게 말하자면 제 1, 2, 3, 4분면으로 나눠서 사분면마다 그 전의 사분면만큼의 숫자를 더해주는 로직이다. 

 

말로 하면 어려우니까 N은 3에서 7행 7열을 예를 들어보겠슴니다.

 

1. N = 3 일때

 

여기서 7행 7열은 제 4사분면이다.

 

 

2. N = 2일 때

이제 위의 4사분면만 잘라서 다시 가져온다면 아래와 같다.

N이 3이었을 때, 한 사분면에는 16개씩 있으며, 1,2,3 을 지나 제 4사분면은 16 * 3인 48부터 시작하게된다. 

 

4분면만 잘랐기 때문에 7행 7열에서 4씩 뺀, 3행 3열에 위치한 사분면을 찾으면 된다. 

보게 되면 이번에도 제 4사분면이다. 

 

여기서도 1, 2, 3을 지났기 때문에 제 4사분면은 48(기존) + 12(한 사분면의 넓이) = 60부터 시작한다. 

 

 

이런식으로 길이가 1이 될때까지 사분면을 찾고, 해당 사분면이 시작하는 숫자를 계산하고를 재귀함수로 만들어서 길이가 계산하는 테이블의 길이가 1이 될때까지 실행시키다보면 원하는 행과 열에 위치한 숫자의 값이 나온다. 

 

코드는 다음과 같다.

let readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  const [n, r, c] = input[0].split(" ").map(Number);
  let answer = 0;
  let tableLength = Math.pow(2, n);

  function getQuad(x, y, length) {
    if (length < 1) return;

    const half = length / 2;
    const skip = half * half;

    if (x < half && y < half) {
      // 1사분면
      getQuad(x, y, length / 2);
    } else if (x >= half && y < half) {
      // 2사분면
      answer += skip;
      getQuad(x - half, y, length / 2);
    } else if (x < half && y >= half) {
      // 3사분면
      answer += skip * 2;
      getQuad(x, y - half, length / 2);
    } else {
      // 4사분면
      answer += skip * 3;
      getQuad(x - half, y - half, length / 2);
    }
  }
  getQuad(c, r, tableLength);

  console.log(answer);
});

 

 

 

📚 참고자료

https://velog.io/@cada/BOJ-1074-Z