백준 17286 - 유미 (파이썬)

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

풀이

이 문제는 브루트포스를 활용하여 최소 이동 거리를 찾는 문제이다.

주어진 네개의 좌표 중 첫번째 좌표에서 시작하여 나머지 세 좌표를 방문하는 모든 순열을 확인하며, 그중 최소 이동 거리를 찾는 방식이다.

for permutation in permutations([1, 2, 3], 3):

itertools.permutations([1, 2, 3] , 3)을 사용하여 첫 번째 좌표를 제외한 나머지 세 좌표의 모든 방문 순서를 생성한다.

• (1, 2, 3), (1, 3, 2), (2, 1, 3) 등 6가지가 존재

x = X[0]
y = Y[0]
move = 0
for i in permutation:
    move += (abs(x - X[i]) ** 2 + abs(y - Y[i]) ** 2) ** 0.5
    x = X[i]
    y = Y[i]

시작점을 X[0], Y[0]로 설정하고, 각 순열에 대해 이동거리를 유클리드 거리 공식을 사용해서 move에 저장한다.

코드

# 백준 17286 - 유미
# 분류 : 브루스포스

from itertools import permutations

X = []
Y = []
for _ in range(4) :
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

min_move = 1e9
for permutation in permutations([1, 2, 3], 3) :
    x = X[0]
    y = Y[0]

    move = 0
    for i in permutation :
        move += (abs(x - X[i]) ** 2 + abs(y - Y[i]) ** 2) ** 0.5
        x = X[i]
        y = Y[i]
    
    min_move = min(min_move, int(move))

print(min_move)