[BaekJoon] 1074번 - Z [Java][C++]

문제 링크

---

1. 아이디어

2차원 배열의 특정 좌표를 Z모양으로 탐색 시 몇 번째로 방문하는지 구하는 문제로 분할 정복을 활용하면 해결할 수 있다. 현재 바라보는 배열을 중앙을 기준으로 십자 모양으로 분할했을 때, 각 영역은 한 단계 작은 2차원 배열을 동일하게 Z모양으로 탐색하는 꼴이라서 재귀로 풀어낼 수 있으며 좌표 정보가 주어지므로 해당 좌표가 분할한 영역중 어디에 포함되는지는 알 수 있다. 따라서 좌표가 포함되는 영역은 더 작은 2차원 배열로 계산을 내려보내고 현재 바라보는 배열에서는 탐색에서 제외한 곳들은 영역의 크기를 알 수 있으니 바로 탐색 수를 더해서 반환해줬다. 이때 더 작은 2차원 배열로 분할 정복할 때 좌표 처리에만 주의해주면 된다.

예를 들어 아래와 같이 2차원 배열의 우측 하단 영역에 좌표가 위치할 경우, 해당 좌표의 방문 순서는 $3 \times len^2$ 만큼은 굳이 탐색할 필요없이 확실히 거쳐가는 것을 알 수 있고 추가로 더 작은 2차원 배열에서 해당 좌표의 방문 순서를 더해준 것과 같다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        System.out.println(dfs(n, r, c));
    }

    static int dfs(int n, int r, int c) {
        if (n == 0) return 0;

        int len = 1 << (n - 1);
        int area = len * len;

        if (r < len) {
            if (c < len) {
                return dfs(n - 1, r, c);
            } else {
                return area + dfs(n - 1, r, c - len);
            }
        } else {
            if (c < len) {
                return area * 2 + dfs(n - 1, r - len, c);
            } else {
                return area * 3 + dfs(n - 1, r - len, c - len);
            }
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int dfs(int n, int r, int c) {
    if (n == 0) return 0;

    int len = 1 << (n - 1);
    int area = len * len;

    if (r < len) {
        if (c < len) {
            return dfs(n - 1, r, c);
        } else {
            return area + dfs(n - 1, r, c - len);
        }
    } else {
        if (c < len) {
            return area * 2 + dfs(n - 1, r - len, c);
        } else {
            return area * 3 + dfs(n - 1, r - len, c - len);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, r, c;
    cin >> n >> r >> c;
    cout << dfs(n, r, c);
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---