[코딩테스트][백준] 🔥 백준 5405번 "프랙탈 거리" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 120분

import math

def findPos(num,r):
    width=2**r
    sx,sy=0,0
    pattern=-1
    startAreaNum=1
    patternBoard={1:(0,0) ,2:(0,1),3:(1,1),4:(1,0)}
    while True:
        if width==1:
            break
        
        if num<startAreaNum+(width//2)*(width//2):
            pattern=1
        elif num<startAreaNum+(width//2)*(width//2)*2:
            pattern=2
        elif num<startAreaNum+(width//2)*(width//2)*3:
            pattern=3
        elif num<startAreaNum+(width//2)*(width//2)*4:
            pattern=4
        
        sx,sy=sx+patternBoard[pattern][0]*(width//2),sy+patternBoard[pattern][1]*(width//2)
        startAreaNum+=(width//2)*(width//2)*(pattern-1)


        if pattern==1:
            patternBoard[2],patternBoard[4]=patternBoard[4],patternBoard[2]
        if pattern==4:
            patternBoard[1],patternBoard[3]=patternBoard[3],patternBoard[1]

        width=width//2
    return sx,sy

for _ in range(int(input())):
    n,h,o=map(int,input().split())
    x1,y1=findPos(h,n)
    x2,y2=findPos(o,n)
    k=(abs(x1-x2)*10)**2+(abs(y1-y2)*10)**2
    print(round(math.sqrt(k)))

힐베르트 곡선: 좌표 거리 계산하기! 🌀📏

힐베르트 곡선에 대해서 문제링크에서의 그림과 같이 패턴이 주어질 때, 해당 번호의 좌표끼리의 거리를 구하는 문제이다. 글을 쓰다보니 뭐가 프랙탈 거리라는지 모르겠다... 게임 이름인가?

처음에는 단순히 분할 정복문제인거처럼 접근하였다. 해당 숫자가 속한 각 사분면에 따라 좌표값을 줄여가면서 하였으나 단순하게는 되지 않았다. 패턴이 들어갈 때마다 바뀌기 때문이다.

그래서 생각해보다가 도달한 것이 패턴의 규칙을 먼저 파악하는것이었다. 처음의 패턴에 시작점부터 끝지점을 1~4라고 할 때, 1~4가 ㄷ자를 뒤집은 모양으로 패턴화할 수 있다. 이 때, 각 사분면에 대해서 분할해 들어갈 때, 1,4번 패턴은 각 2번,4번과 1번, 3번 위치를 바꾸면서 들어간다. 문제에서 주어진 n=3일 때 그림을 보면 이해가 될 것이다. 그렇기 때문에 먼저 현재 들어갈 곳의 범위를 줄이고 그 다음 패턴을 맞춰서 바꿔야 한다. 후에 그 패턴에 따라 숫자 범위를 줄여나가고 좌표 값을 조정해야 한다.

이렇게 Python으로 백준의 "프랙탈 거리" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊