백준 1891 파이썬 사분면

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

1891번: 사분면

d, num = input().split()
d = int(d)
x,y = map(int,input().split())

def find_coordinate(num,idx,r,c,size):
    if size == 0:
        global num_r,num_c
        num_r,num_c = r,c
        return

    if num[idx] == '1':
        find_coordinate(num,idx+1,r,c+size,size//2)
    elif num[idx] == '2':
        find_coordinate(num,idx+1,r,c,size//2)
    elif num[idx] == '3':
        find_coordinate(num,idx+1,r+size,c,size//2)
    elif num[idx] == '4':
        find_coordinate(num,idx+1,r+size,c+size,size//2)

def make_answer(num_r,num_c,size,ans):
    if size == 0:
        print(ans)
        return

    if 0 <= num_r < size and size <= num_c < 2*size:
        make_answer(num_r,num_c-size,size//2,ans+'1')
    elif 0 <= num_r < size and 0 <= num_c < size:
        make_answer(num_r, num_c, size//2, ans+'2')
    elif size <= num_r < 2*size and 0 <= num_c < size:
        make_answer(num_r-size, num_c, size//2, ans+'3')
    elif size <= num_r < 2*size and size <= num_c < 2*size:
        make_answer(num_r-size,num_c-size,size//2,ans+'4')

num_r = num_c = 0
find_coordinate(num,0,num_r,num_c,(2**d)//2)
num_r -= y
num_c += x
if 0 <= num_r < 2**d and 0 <= num_c < 2**d:
    make_answer(num_r,num_c,(2**d)//2,'')
else:
    print(-1)

번호의 좌표를 찾아낸 후, 이동시킨다음 이동된 좌표를 이용해 답을 구해내면 된다.

예를들어 num(번호) = 341 일때, 좌표는 8*8 격자 안에 존재할 것이다.

좌표 [0,0], idx=0 부터 시작한다. num[idx]=3 이므로 3사분면에 존재한다.

따라서 좌표는 [0+size,0], idx +=1 이 된다. 재귀적으로 반복하여 좌표를 찾아간다.

size가 0이되면 종료한다.

 

구해낸 좌표를 이동시킨다. 만약 이동이 격자 안의 범위를 벗어났다면 -1을 출력한다.

 

이동시킨 좌표에서 시작한다. size를 이용해서 현재 몇사분면인지 구한다음 ans에 더해주고, 좌표값을 조정해준다.

재귀적으로 반복하여 답을 구해낸다.