Baekjoon Training #1891

---

#1891 사분면

Source Code

d, num = input().split() # d: 총 단계 수, num: 이동 경로를 나타내는 문자열
d = int(d) # d를 정수형으로 변환
x, y = map(int, input().split()) # x: 가로 이동거리, y: 세로 이동거리
size = (2**d)

def find(num, idx, curX, curY, size):
    # 단계가 0이 되면 현재 좌표를 기억하고 리턴
    if size == 0:
        # 전역 변수선언 
        global tarX, tarY
        tarX, tarY = curX, curY # 타겟 좌표 설정
        return

    # 자리수별로 번호에 따른 다음 이동을 찾아 재귀 호출
    if num[idx] == '1':
        find(num, idx+1, curX+size, curY+size, size//2)
    elif num[idx] == '2':
        find(num, idx+1, curX, curY+size, size//2)
    elif num[idx] == '3':
        find(num, idx+1, curX, curY, size//2)
    elif num[idx] == '4':
        find(num, idx+1, curX+size, curY, size//2)

# 좌표로 정답 숫자열을 찾는 translate함수
def translate(tarX, tarY, size, ans):
    # 단계가 0이 되면 정답 출력하고 리턴
    if size == 0:
        print(ans)
        return

    # 좌표를 바탕으로 size를 기준으로 단위 사각형을 찾아나감
    if size <= tarX < 2*size and size <= tarY < 2*size:
        translate(tarX-size, tarY-size, size//2, ans+'1')
    elif 0 <= tarX < size and size <= tarY < 2*size:
        translate(tarX, tarY-size, size//2, ans+'2')
    elif 0 <= tarX < size and 0 <= tarY < size:
        translate(tarX, tarY, size//2, ans+'3')
    elif size <= tarX < 2*size and 0 <= tarY < size:
        translate(tarX-size, tarY, size//2, ans+'4')

# 초기좌표 잡기
tarX = tarY = 0
find(num, 0, tarX, tarY, size//2)

# 이동거리만큼 좌표 이동
tarX += x
tarY += y

# 좌표가 범위내인지 체크
if 0 <= tarX < size and 0 <= tarY < size:
    translate(tarX, tarY, size//2, '')
else:
    print(-1)

Divide & Conquer 알고리즘의 특징이 잘 드러나는 문제이다. 우선 입력받은 숫자에 따라 사각형이 얼마나 나눠질 수 있을지 판단하다. 그후에 find를 통해 현재 숫자를 좌표화 시켜준뒤 주어진 이동 횟수만큼 좌표를 바꿔서 target을 찾는다. 그후 좌표를 다시 숫자열로 해석하여 변환해주는 translate함수를 통해 정답을 찾아낸다. find, check함수는 글을 통해서는 이해하기 어려우므로 그림을 통해 살펴보자.

 

find()함수에서 예시를 통해보면 초기 숫자가 341인 경우이다.

0번 인덱스 즉 자리수가 가장 큰 숫자부터 조사하여 숫자에 알맞는 위치이동을 한다. 이때 이동하는 거리는 인덱스 조사가 넘어감에 따라 1/2해주어 알맞게 이동할 수 있도록한다. 좌하단에서 시작하기에 3이 들어올때 제자리인 것이고 이는 시작하는 위치에 따라 코드를 다르게 작성해야한다.

 

다음으로 translate()함수를 보자.

찾은 (5,2)좌표를 해석해 정답인 424를 찾는 과정이다.

424는 코드의 좌표상 (5,2)이다.

case분류의 기준인 size는 계속해서 반감해서 원하는 사각형을 찾고 좌표도 재조정하여 결국 최소 단위의 사각형까지 줄어들면 함수가 값을 출력한다.

---