[Beakjoon] 1074번 Z

📣
Beakjoon에서 PASS된 코드만 업데이트합니다.
알고리즘을 먼저 풀이하는 언어(Java)가 정해져있어, 풀이 언어(Python, C++, Java)가 모두 업데이트될 때까지는 시간이 걸릴 수 있습니다.

문제 제시

---

문제

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다.
예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 2² × 2² 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c ≤ 2^N

문제 풀이

---

입력한 좌표가 몇번째 방문하는 곳인지 출력하는 문제입니다.
각 방에 도달하는 순차가 어떤지 살펴봐야합니다.

접근방법 1 : 실제로 정해진 규칙대로 방문하면서 해당 r, c와 동일해질 때 해당 순번을 반환한다.
접근방법 2 : 크게 4가지의 영역으로 나누어지니 특징을 찾아 진행한다.

처음 문제를 분석하면 이렇게 2가지의 방법을 생각하게 됩니다.
사실 생각나는 모든 방법을 구현해보고자하는게 제 공부방법이지만,
방법1의 경우는 사이즈가 조정되면서 계산하는 것이 더 어렵게 느껴졌습니다.
따라서 방법 2번으로 풀이를 진행하였습니다.

우선 가장 큰 특징을 먼저 보겠습니다.
N이 정해지면 2^N이 정해지고, 그럼 한 변의 길이가 금방 구해지게 됩니다.
그럼 조금 상세하게 알아보겠습니다.

현재의 모양을 갖고 있는 Z 공간을 저희는 알고 있습니다.
접근방법 2의 내용대로 차근차근 그 범위를 좁혀보겠습니다.
저희는 i=1, j=2일 때의 6의 값을 구해봅시다.

규칙을 찾을 때, 가장 큰 특징은 너무 풀어쓰지 않는게 중요하다고 생각합니다.
주어진 값, 그대로를 하는게 나중에 코드로 적을 때 편한거 같더라구요.
처음에 가장 중요한 것은 1~4사분면의 경계를 잘 확인해서 알맞는 영역에 들어가는 것입니다.
현재 저희는 각 시작값을 구하기 위해서 한 변의 값과 연결 지어보겠습니다

지금의 분류를 통해 2사분면에 저희가 원하는 i=1, j=2이 속해있으니,
저 영역으로 상세를 확인해봅니다.

현재의 영역에서는 각 i, j에 완벽하게 일치하는 값이 생겼습니다!
더 상세하게 영역을 확인할 필요가 없겠습니다.
검사를 멈추는 조건은 i,j가 완벽하게 일치할 때도 있지만, 한 변의 길이가 1이 될때라고 생각해도 되겠죠!
이 조건은 본인이 편한대로 하시면 될 것 같습니다.

이미 이전에 값을 구할 수 있기에, 지금 구하는 값은 중첩하는 값으로 진행해보고자하는데,
0,1,2,3 을 현재 알고 있는 값과 연관지어야 하는게 어렵네요.
지금 알고 있는 건 한변의 길이와 연관짓는게 제일 좋을 것같아서 위처럼 한변/2 * 사분면으로 정리했습니다.
그럼 이전 단계의 내용도 수정을 해줘야겠죠.

현재 고치려고 보니 한변/2 * 사분면도 불가능 합니다.
그렇다면 조금 조작을 해보려고 생각을 해보니, 한변/2 * 한변/2 * 사분면으로 하면 가능하다는 사실을 확인할 수 있죠.

이렇게 다시 다음 단계를 수정하면, 한변/2 * 한변/2 * 사분면으로 모두 적용이 가능합니다.
이제 이를 코드로 작성하면 되겠습니다.

문제 코드

Java

제출 결과