[백준] 1074번 - Z — 멈추지 않는 기록

728x90

문제 링크 : https://www.acmicpc.net/problem/1074

| 문제 탐색하기

1) 목표

: N, r, c가 주어졌을 때, r행 c열을 몇 번째로 방문했는지 출력하기

2) 기능 명세서

(1) 숫자 입력받기

N, r, c를 한 줄에 공백으로 입력받는다.
입력 문자열을 공백 기준으로 분리한 뒤, 숫자 배열로 변환하여 저장한다.

(2) 배열을 변수로 관리하기

입력받은 배열을 구조 분해 할당을 사용하여 N, r, c 변수로 각각 관리한다.

(3) N > 0 동안 반복 수행

N이 0이 될 때까지 반복문을 실행한다.
각 반복마다 현재 배열을 4개의 사분면으로 분할하여 (r, c)가 속한 사분면을 판별한다.

(4) 사분면 판별 기준

현재 단계에서 half = 2^(N-1) 로 설정한다.

사분면	조건
1사분면 (좌상)	r < half && c < half
2사분면 (우상)	r < half && c >= half
3사분면 (좌하)	r >= half && c < half
4사분면 (우하)	r >= half && c >= half

(5) 방문 순서 누적 계산

각 사분면은 Z 순서에 따라 앞선 사분면의 칸 수만큼 건너뛰게 되므로, 사분면에 따라 결과값에 다음을 누적한다.

사분면	누적 값
1사분면	0
2사분면	size
3사분면	size * 2
4사분면	size * 3

단, size = half * half

(6) 좌표 보정

선택된 사분면 내부를 새로운 기준으로 삼기 위해 좌표를 보정한다.

사분면	좌표 보정
1사분면	변화 없음
2사분면	c -= half
3사분면	r -= half
4사분면	r -= half, c -= half

(7) 단계 축소

한 단계의 사분면 계산이 끝나면 N = N - 1 로 줄여 다음 반복을 수행한다.

(8) 결과 출력

모든 반복이 종료되면, 누적된 결과값을 출력하여 (r, c) 좌표의 Z 순서 방문 인덱스를 반환한다.

| 고민이 되었던 부분

1) N, r, c와의 관계를 어떻게 구할까?

: 처음에는 (N, r, c) 사이의 관계를 하나의 수식이나 방정식으로 표현할 수 있지 않을까 고민했다. Z 순서는 분명한 규칙성을 가지고 있으므로, 이를 일반화한 수식이 존재할 것이라 생각했기 때문이다. 그러나 실제로 접근해보니, 좌표의 위치에 따라 경우의 수가 지나치게 많아지면서 단일 방정식으로 문제를 해결하는 방식은 적절하지 않다는 결론에 이르렀다.

이후 문제에서 제시한 힌트인 “N > 1인 경우, 배열을 크기가 2⁽ᴺ⁻¹⁾ × 2⁽ᴺ⁻¹⁾ 인 정사각형 4개로 분할한 후, 이를 재귀적으로 순서대로 방문한다.” 라는 문장을 다시 살펴보게 되었다. 이 문장을 통해, 이 문제의 핵심은 개별 좌표 자체가 아니라 영역의 크기와 사분면 단위의 분할에 있다는 점을 깨닫게 되었다.

이를 N = 3인 경우로 예시를 들어 설명해보면, 배열 한 변의 길이는 2³이 되고, 전체 칸의 개수는 (2³) × (2³) = 64개가 된다. 이 배열을 문제의 설명대로 4개의 사분면으로 나누면, 각 사분면은 (2²) × (2²) = 16개의 칸을 가지게 된다.

즉, 배열 한 변의 절반 크기를 기준으로 (r, c) 좌표가 어느 사분면에 속하는지를 판단하고, 그 사분면 이전에 방문된 사분면들의 칸 수만큼을 초기값에 누적해 나가면 원하는 방문 순서를 계산할 수 있다고 판단했다.

| 처음 코드 & 개선이 필요한 점

function printResult(inputs) {
  let [N, r, c] = inputs;
  let result = 0;

  while (N > 0) {
    const half = 2 ** (N - 1);
    const size = half * half;

    if (r < half && c < half) {
      // 1사분면 (0)
    } else if (r < half && c >= half) {
      // 2사분면 (1)
      result += size;
      c -= half;
    } else if (r >= half && c < half) {
      // 3사분면 (2)
      result += size * 2;
      r -= half;
    } else if (r >= half && c >= half) {
      // 4사분면 (3)
      result += size * 3;
      r -= half;
      c -= half;
    }
    N--;
  }

  return result;
}

function main() {
  const fs = require("fs");
  const input = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);
  const output = printResult(input);
  console.log(output);
}

if (require.main === module) {
  main();
}

module.exports = {
  printResult,
};

1) 사분별 판펼 로직의 가독성

: 현재 코드는 사분면을 여러 개의 If문과 else if 문으로 판별하고 있다. 또한, 각각의 조건문에 들어가는 수식과 실행되는 배수 적용 및 행과 열의 차감 로직도 비슷하다. 그래서 사분변 판별 로직을 개선해서, 몇 사분면에 있는지를 삼항 연산자로 개선한 뒤, 누적 값을 계싼하고, 좌표 보정 값도 단순하게 하면 좋을 것 같았다.

| 최종 코드

function printResult(inputs) {
  let [N, r, c] = inputs;
  let result = 0;

  while (N > 0) {
    const half = 2 ** (N - 1);
    const size = half * half;

    // 사분면 번호 계산
    const quadrant = (r >= half ? 2 : 0) + (c >= half ? 1 : 0);

    // 누적 값 계산
    result += size * quadrant;

    // 좌표 보정
    if (r >= half) r -= half;
    if (c >= half) c -= half;

    N--;
  }

  return result;
}

function main() {
  const fs = require("fs");
  const input = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);
  const output = printResult(input);
  console.log(output);
}

if (require.main === module) {
  main();
}

module.exports = {
  printResult,
};

| 느낀점

골드5 문제를 처음 풀어보며서 "정말 골드는 골드다"라는 생각이 들었다. 물론 골드 중에서도 조금 쉬운 편에 속한 문제라 생각하고, 잘 얻어걸렸다고 생각하려고 하는데, 더 알고리즘에 대한 생각을 길러 나가고 싶다. 특히나 도출해내내는 그 과정이 너무나도 어려운 것 같다. 더 기능 명세서를 작성하면서 알고리즘을 탄탄하게 만들고 싶다.