알고리즘
[백준] Z(1074)
45 views
블로그 불러오는 중...
알고리즘
백준 Z(1074) 문제 풀이
https://www.acmicpc.net/problem/1074
백준 1074번 - Z 문제는 2^N × 2^N 크기의 배열을 Z 모양으로 탐색할 때, 특정 좌표 (R, C)가 몇 번째로 방문되는지를 구하는 문제다.
처음엔 재귀로 모든 경우를 탐색하면서 하나씩 카운트하는 방식으로 풀었는데, 백준의 시간 제한(0.5초) 때문에 실패했다.
그래서 탐색 횟수를 줄이는 방법을 고민했고, 문제를 4개의 사분면으로 나눠서 접근하는 접근하게 되었다.
그래서 생각했던 방식은, 케이스 크기를 줄여야 했다.
먼저 그림을 보면 다음과 같다.
크게 보면 사분면으로 나누어 진다.
그래서, 좌표가 어떤 사분면에 들어있는지 파악하고
지금 보면, 위에 사진의 경우에 N = 3 이다.
그림을 보면 배열을 1, 2, 3, 4 사분면으로 나눌 수 있다.
그리고 각 사분면의 시작 인덱스를 보면 다음과 같은 규칙이 나온다.
0163248즉, (R, C)가 어느 사분면에 속하는지 확인한 다음, 해당 사분면의 시작 값만큼 답에 더해주고, 다시 그 사분면을 쪼개면서 n = 1이 될 때까지 반복하면 된다.
해당 사분면을 기준으로 2→ 1 → 3 → 4 순서대로 2 ** (n) 만큼 정답에 더하고, 그 사분면을 다시 쪼개며 n = 1 이 될때까지 반복하면 된다.
재귀를 돌리면서 크기를 축소했으므로, 축소할 때마다 다음 재귀를 돌리는 행과 열도 축소 해 주어야 한다.
const input =
process.platform === "linux"
? require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
: require("fs").readFileSync("./input.txt").toString().trim().split("\r\n");
const [N, R, C] = input[0].split(" ").map((el) => parseInt(el));
let answer = 0;
const visit = (n, r, c) => {
if (n < 1) return;
const splitedSize = (2 ** (n - 1)) ** 2;
if (0 <= r && r < 2 ** (n - 1) && 2 ** (n - 1) <= c && c < 2 ** (n - 1)) {
answer = answer + splitedSize;
visit(n - 1, r, c - 2 ** (n - 1));
}
if (2 ** (n - 1) <= r && r < 2 ** n && 2 ** (n - 1) <= c && c < 2 ** n) {
answer = answer + 3 * splitedSize;
visit(n - 1, r - 2 ** (n - 1), c - 2 ** (n - 1));
}
if (2 ** (n - 1) <= r && r < 2 ** n && 0 <= c && c < 2 ** (n - 1)) {
answer = answer + 2 * splitedSize;
visit(n - 1, r - 2 ** (n - 1), c);
}
if (0 <= r && r < 2 ** (n - 1) && 0 <= c && c < 2 ** (n - 1)) {
visit(n - 1, r, c);
}
};
visit(N, R, C);
console.log(answer);