. ㅋ (백준 1074번 : Z)
본문 바로가기
카테고리 없음

ㅋ (백준 1074번 : Z)

by 불냥이_ 2020. 12. 14.

 

1074번: Z (acmicpc.net)

 

1074번: Z

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

www.acmicpc.net

일단 N이 2가 될때까지 쪼개야 한다. 

이를 재귀로 표현하면 다음과 같다.

    if N = 2:

    else:
        zet(N-1,r,c):

 

그리고 (r,c)가 몇 사분면에 있는지가 필요하다. ( Z방향으로 n사분면을 정한다.)

만약 첫 시도에서 (r,c)가 1사분면에 있지 않다면 바로 구할 수 있으나, 1사분면에 있다면 한번 더 쪼개줘야 한다. 

def zet(N, x, y):
    
    if x > N // 2:
        i = 1
    else:
        i = 0

    if c > N // 2:
        j = 1
    else:
        j = 0

    xy = [i, j]

    for l in range(0,1):
        for k in range(0,1):
            if xy != [k, l]:
                count += 1
            else:
                break
        if xy != [k,l]:
            break

 

그리고 1사분면에 있지 않을 때 방문 횟수를 구해보자.

일단 2 ^ (N-1) * 2 ^ (N-1) * (n사분면의 n -1)이 기본으로 들어가는 방문횟수이다. 

그리고 해당 사분면에서 다시 한번 쪼개줘야 할 것이다. 

또한, 쪼개지면서 각 좌표를 수정할 필요가 있다. (해당 위치에서 다시 사분면을 나누고 (x,y)가 쪼개진 Z안의 몇사분면이 있는지 알기위해서.)

    else:
        res = 2**(N)+n
        if count == 0:
            zet(N-1,x-N//2, y-N//2)
        
        elif count == 1:
            zet(N-1,x-N//2, y)
        
        elif count == 2:
            zet(N-1, x, y-N//2)

        else count == 3:
            zet(N-1, x, y-N//2)

 

이러면 N=2가 될때까지 쪼개질 것이다. N=2일 때, 해당 위치가 몇사분면에 있는지 알아보자.

 

        if N == 2:
            if x == 0 and y == 0:
                num = 0

            elif x == 1 and y == 0:
                num = 1

            elif x == 0 and y == 1:
                num = 2

            else:
                num = 3

            return num

num를 기반으로 방문 횟수를 구할 수 있으므로 식을 적어준다. 또한, 재귀함수를 실행함에 있어서 계속 넘겨줄 수 있도록 고안한다. 

 

 		else:
            res = 2**(N)*n
            if count == 0:
                return num + zet(N-1,x-N//2, y-N//2)
        
            elif count == 1:
                return num + zet(N-1,x-N//2, y)
        
            elif count == 2:
                return num + zet(N-1, x, y-N//2)

            else:
                return num + zet(N-1, x, y-N//2)

이제 기본 플로우를 정해보자.

점이 몇 사분면에 있는지 판단하여, 기본 방문 횟수를 정한다. (Z방향으로 0, 1, 2, 3사분면을 정한다.)

2 ^ (N-1) * 2 ^ (N-1) * (n사분면의 n -1)

 

그리고 해당 사분면을 쪼개주고, 좌표를 수정한다.

 

 

 

 

일단 기본 코드는 하기와 같다. (물론 실행하니 답이 나오지 않았다.)

N, r, c = map(int,input().split())

def zet(N, x, y):
    n=0
    if N == 1:
        if x == 0 and y == 0:
            return 0

        elif x == 1 and y == 0:
            return 1

        elif x == 0 and y == 1:
            return 2

        else:
            return 3

    else:
        if x == N // 2 and y == N // 2:
            n = 0
            return 2**(N)*n + zet(N-1, x - N//2, y - N//2)

        elif x == N // 2 and y == N // 2:
            n = 1
            return 2**(N)*n + zet(N-1, x - N//2, y)

        elif x == N // 2 and y == N // 2:
            n = 2
            return 2**(N)*n + zet(N-1, x, y - N//2)

        else:
            n = 3
            return 2**(N)*n + zet(N-1, x, y - N//2)
    
        
print(zet(N, r, c))

2,3,1을 넣었더니 15가 나왔다.

무엇이 문제일까. 천천히 따라가보기로 한다. 

 

N=2에 (3,1)이 된다.

3,1은 1사분면에 있으나, 파이썬에서 print에서 확인해보니 3사분면이 나왔다. 분류식이 잘못된 것이다.

생각해보니 등호가 아니라 부등호를 넣어줘야한다. 또한 한변의 길이가 2^n이므로 2로 나눠줄 필요가 없다.

(또 행열이 바뀌었다 ㅡ.ㅡ)

 

수정해보았다.

import sys

N, r, c = map(int,input().split())

def zet(N, x, y):
    n=0
    if N == 1:
        if x == 0 and y == 0:
            return 0

        elif x == 1 and y == 0:
            return 1

        elif x == 0 and y == 1:
            return 2

        else:
            return 3

    else:
        
        if x <  N and y <  N:
            print("0사분면")
            n = 0
            return 2**(N)*n + zet(N-1, x - N//2, y - N//2)

        elif x >=  N and y <  N:
            print("1사분면")
            n = 1
            return 2**(N)*n + zet(N-1, x - N//2, y)

        elif x <  N and y >=  N:
            print("2사분면")
            n = 2
            return 2**(N)*n + zet(N-1, x, y - N//2)

        else:
            print("3사분면")
            n = 3
            return 2**(N)*n + zet(N-1, x, y - N//2)
    
        
print(zet(N, c, r))

2,3,1의 경우 11은 제대로 나왔으나 3 7 7 은 제대로 나오지 않았다.

경로는 3사분면-3사분면-3사분면 들어간 것을 보니 제대로 들어갔다.

 

차근히 검산 해보니 여러곳에서 문제가 있었다. 수정은 다음과 같다.

import sys




N, r, c = map(int,input().split())

def zet(N, x, y):
    n=0
    if N == 1:
        if x == 0 and y == 0:
            #print("0사분면")
            return 0

        elif x == 1 and y == 0:
            #print("1사분면")
            return 1

        elif x == 0 and y == 1:
            #print("2사분면")
            return 2

        else:
            #print("3사분면")
            return 3

    else:
        
        if x <  2**(N-1) and y <  2**(N-1):
            #print("0사분면")
            n = 0
            return 2**(N-1)*2**(N-1)*n + zet(N-1, x, y)

        elif x >=  2**(N-1) and y <  2**(N-1):
            #print("1사분면")
            n = 1
            return 2**(N-1)*2**(N-1)*n + zet(N-1, x - 2**(N-1), y)

        elif x <  2**(N-1) and y >=  2**(N-1):
            #print("2사분면")
            n = 2
            return 2**(N-1)*2**(N-1)*n + zet(N-1, x, y - 2**(N-1))

        else:
            #print("3사분면")
            n = 3
            return 2**(N-1)*2**(N-1)*n + zet(N-1, x - 2**(N-1), y - 2**(N-1))
    
        
print(zet(N, c, r))

 

심사 결과 패스했다. 

댓글