[백준 Python Swift] 1074번 Z

1074번 Z

• 문제바로가기

풀이 방법

• N >= 2일 때(4 by 4 행렬부터), 행과 열을 절반(2**N / 2)씩 쪼개는데
  • 2 by 2 행렬이 될 때까지 쪼갠다(2 by 2 행렬에서는 Z 모양으로 방문하면 된다)
• 2 by 2 행렬이 아닐 때는 좌상 -> 우상 -> 좌하 -> 우하 순으로 방문해야한다
• 단, 전부 방문하면서 찾으면 시간초과가 난다
  • 따라서 쪼갤 때 범위를 나누어 절대 없을 부분은 넘어가고
  • 있을 것 같은 부분에서만 찾으면 된다

풀이

Python

def solve(n, x, y):
    global count
    # 2 by 2 행렬부터는 Z 모양으로 방문
    if n == 2:
        if x == row and y == column:
            print(count)
            return
        count += 1
        if x == row and y+1 == column:
            print(count)
            return
        count += 1
        if x+1 == row and y == column:
            print(count)
            return
        count += 1
        if x+1 == row and y+1 == column:
            print(count)
            return
        count += 1
        return
    else:
        # 여기서부터 다 탐색하면 시간초과
        # 있을 것 같은 부분에서만 탐색하면 된다
        if row < x + n / 2 and column < y + n / 2:
            solve(n / 2, x, y)
        elif row < x + n / 2 and column < (y + n / 2) + n / 2:
            count += int(((n / 2) ** 2))
            solve(n / 2, x, y + n / 2)
        elif row < (x + n / 2) + n / 2 and column < y + n / 2:
            count += int((((n / 2) ** 2))*2)
            solve(n / 2, x + n / 2, y)
        elif row < (x + n / 2) + n / 2 and column < (y + n / 2) + n / 2:
            count += int((((n / 2) ** 2))*3)
            solve(n / 2, x + n / 2, y + n / 2)
    
N, row, column = map(int, input().split(" "))
count = 0
solve(2**N, 0, 0)

Swift

import Foundation

let inputNRC = readLine()!.split(separator: " ")

let N = Int(inputNRC[0])!
let row = Int(inputNRC[1])!
let column = Int(inputNRC[2])!

var count = 0

func solve(_ n: Int, _ x: Int, _ y: Int) -> Void {
    
    if n == 2 {
        if x == row, y == column {
            print(count)
            return
        }
        count += 1
        if x == row, y+1 == column {
            print(count)
            return
        }
        count += 1
        if x+1 == row, y == column {
            print(count)
            return
        }
        count += 1
        if x+1 == row, y+1 == column {
            print(count)
            return
        }
        count += 1
        return
    } else {
        if row < x + n / 2, column < y + n / 2 {
            solve(n / 2, x, y)
        } else if row < x + n / 2, column < (y + n / 2) + n / 2 {
            count += (n / 2) * (n / 2)
            solve(n / 2, x, y + n / 2)
        } else if row < (x + n / 2) + n / 2, column < y + n / 2 {
            count += (n / 2) * (n / 2) * 2
            solve(n / 2, x + n / 2, y)
        } else {
            count += (n / 2) * (n / 2) * 3
            solve(n / 2, x + n / 2, y + n / 2)
        }
    }
}

solve(Int(pow(2, Double(N))), 0, 0)