1074번: Z

1074번: Z

Z

 

문제

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

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

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

 

 

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

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

 

입력

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

출력

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

제한

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

예제 입력 1 

2 3 1

예제 출력 1 

11

---

풀이

 

문제를 확인해보면,

1. 2^N * 2^N 크기의 2차원 배열을 Z 모양으로 탐색하자.
2. 입력받은 r행과 c열을 몇 번째로 탐색하는지 출력하자.

문제는 간단하다. 2차원 배열을 Z 모양으로 탐색하고 입력받은 r행과 c열의 위치에서 몇 번째 탐색인지만 출력하면 된다.

여기서 관건은 "어떻게 탐색할 것인가?"와 "몇 번째 탐색인지 어떻게 판단?" 이다.

 

---

설계

 

문제를 어떻게 하면 간단하게 풀 수 있을까,,, 2차원 배열을 4구역으로 나눠서 풀면 간단할 것 같다.

우선 난 배열을 4구역으로 이렇게 나눴다.

 

 

• 4구역으로 나누고 또 그 안에서 4구역으로 나눈다 => 재귀 호출

 

❗️4구역 중 어디에 속하는지 어떻게 판단? 

1. 우선 배열의 크기를 반으로 나눠보자. => halfsize = size/2
2. 입력받은 r이 halfsize - 1보다 작다면 1, 2사분면이고, 크다면 3, 4 사분면인 걸 확인할 수 있다.
3. 입력받은 c가 halfsize - 1보다 작다면 2, 3사분면이고, 크다면 1, 4사분면인 걸 확인할 수 있다. 

=> 어디에 속하는 지 판단 후, 나눌 수 있을 때까지 재귀 호출 

 

 

❗️4구역을 모두 탐색할 필요가 있을까?

굳이 4구역을 모두 탐색하지 않아도 4구역 중 어디에 속하는지만 판단하여, 해당 배열 크기(halfsize * halfsize)의 

위치에 따라 cnt를 증가시키면 된다.

 

• 1사분면: halfsize * halfsize * 1/4
• 2사분면: x
• 3사분면:  halfsize * halfsize * 2/4
• 4사분면:  halfsize * halfsize * 3/4

=> 어디 구역에 속하는지 판단 후, cnt 증가

 

---

구현

 

위의 설계를 바탕으로 코드를 구현해보자.

 

1. 처음 주어진 2^N*2^N 크기의 배열에서 4구역으로 나눌 수 있을 때까지 재귀 호출

 

• 2^N의 크기를 arrSize에 저장한다.
• 재귀함수는 check(행, 열, size)로 설정한다.

 

 

2. r행과 c열이 4구역 중 어디에 속하는 지 판단

 

• x가 (halfsize - 1) 보다 작다면 => 3, 4사분면
  • y가 (halfsize - 1)보다 크다면 => 4사분면
  • y가 (halfsize- 1)보다 작다면 => 3사분면
• x가 (halfsize- 1) 보다 크다면 => 1, 2사분면
  • y가 (halfsize - 1)보다 크다면 => 1사분면
  • y가 (halfsize - 1)보다 크다면 => 2사분면

 

---

전체코드

 

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}

var(N, r, c) = (input[0], input[1], input[2])
var arrSize = Int(pow(2.0, Float(N)))

var cnt = 0


check(r, c, arrSize)

func check(_ x: Int, _ y: Int, _ size: Int){
    
    if size >= 2 {
        if(x > size/2 - 1) {// 3,4 분면
            if (y > size/2 - 1 ){//4
                cnt += (size * size) * 3/4
                check(x-size/2, y-size/2, size/2)
            }
            else{//3
                cnt += (size * size) * 2/4
                check(x-size/2, y, size/2)
            }
        }
        else {//1,2 분면
            if(y > size/2 - 1){//1
                cnt += (size * size) * 1/4
                check(x, y-size/2, size/2)
            }
            else{//2
                check(x, y, size/2)
            }
        }
    }
}

print(cnt)

 

---

정리

 

 

이 문제는 기저 사례에 도달할 때까지 계속해서 size/2를 하며 재귀 호출을 했다.

=> 즉, 분할 정복을 이용한 문제라고 할 수 있다. 

 

[Algorithm Strategy] - 7. 분할 정복