오늘의 알고리즘(5월 5일)

1. 백준, Z, 1074번 

www.acmicpc.net/problem/1074

1074번: Z

---

2. 생각해보자

a) 문제 이해하기

• 2의 N승 곱하기 2의 N승 크기의 행렬이 있다.
• 행렬의 크기와는 상관없이 2 곱하기 2 크기의 배열로 나누어 방문한다.
• 방문 순서는 Z 모양 순서다. (0, 1, 2, 3 순서로 방문) 
  
• 입력값은 N, r, c 순서대로 주어진다. 
• 입력값 N에 따라서 행렬의 크기가 정해진다. 
• 입력값 r은 row(행), 입력값 c는 column(열)을 의미한다. 
• 주어진 N만큼의 행렬에서 Z 모양으로 방문하는 경우, 주어진 r행 c열을 몇번째로 방문하는지 찾는다.  

 

b) 어떻게 풀까?

• 입력값 N을 이용하여 2차원 배열을 만든다.
• 가장 작은 크기의 배열부터 만들어서 방문 순서의 규칙성을 찾아본다.

예시) 

 

---

3. 코드 풀이 및 분석

 

a) 문제의 핵심

• 2 곱하기 2 행렬은 원래부터 Z모양으로 탐색을 한다. 
• 2 곱하기 2 행렬은 4의 방문순서를 갖는다.
• 입력된 N값을 기준으로 2곱하기 2행렬이 몇개인지 파악한다. 
• 2 곱하기 2 행렬의 크기로 나누어서 탐색을 진행한다. 

 

def solve(n, x, y):
    global result
    if n == 2:
        if x == X and y == Y:
            print(result)
            return
        result += 1

        if x == X and y + 1 == Y:
            print(result)
            return
        result += 1

        if x + 1 == X and y == Y:
            print(result)
            return
        result += 1

        if x + 1 == X and y + 1 == Y:
            print(result)
            return
        result += 1
        return

    // 재귀호출을 이용하여 계속해서 가장 작은 크기의 행렬이 될 때까지 나눈다.
    solve(n / 2, x, y)
    solve(n / 2, x, y + n / 2)
    solve(n / 2, x + n / 2, y)
    solve(n / 2, x + n / 2, y + n / 2)


result = 0
N, X, Y = map(int, input().split(' '))
solve(2 ** N, 0, 0)