[JAVA / 자바] 백준 1074번 - Z (실버 1)

 문제 

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

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

---

 입력 

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

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

---

 출력 

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

---

---

 문제 접근 방법 

이번 문제는 분할 정복(Divide and Conquer) 문제이다.

z모양으로 탐색을 하는데, 최종적으로 n번째로 탐색되는 칸의 숫자를 출력하는 문제이다.

z모양은 다음과 같이 좌상, 우상, 좌하, 우하 총 4가지 영역도 쪼갤 수 있다.

1	2
3	4

문제를 푸는 과정은 문제에서 구하고자 하는 칸 위치를 보고 어느 영역에 속한 칸인지 세부적으로 타고 들어가면 된다.

만약 2번 영역에 속한 칸을 출력하는 것이면 2번 칸의 범위 내에서 다시 4가지 영역으로 나누어 다시 어느 영역으로 진입할 것인지 선택해 계속 이 과정을 반복하다가 영역의 크기가 1이 되면 그때 해당 위치의 번호를 출력해주면 된다.

 

Ex) 3열 1행 구하기

이런 식으로 범위를 1/4씩 줄여가면서 탐색해주면 된다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

항상 분할 정복은 어떻게 분할할지를 정하는 게 제일 어렵지만 그것만 정해지면 쉽게 문제를 해결할 수 있는 것 같다. 마치 다이나믹 프로그래밍 문제에서 점화식을 세우는 느낌,,?이랄까

---

 문제 원본 

https://www.acmicpc.net/problem/1074

1074번: Z

 알고리즘 분류 

• 분할 정복
• 재귀