[Python] 5588번 별자리 찾기

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

5588번: 별자리 찾기

---

 

24/02/01

 

 

간단한 브루트포스 문제로, 집합을 사용해 적절히 구현하면 쉽게 해결할 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

별자리를 구성하는 별들은 리스트로 받고, 사진 속 별 들의 위치는 집합에 넣어주었다.

 

이후 사진 속의 모든 별들 마다 그 별이 옮겨진 별자리의 중심이 된다고 가정하고 이동량을 구해주었다.

 

옮기기 전 별자리에 있는 모든 별 마다 그 이동량을 적용해 주었다. 즉, 옮겨진 별의 좌표를 구했다.

 

그 옮겨진 별의 좌표가 모두 사진 속에 있다면, 우리는 그 이동량을 출력해주기만 하면 된다.

 

각 별마다 그 별이 사진 속에 있는지를 판단하는 연산은 $\mathcal{O}(1)$에 가능하기 때문에 빠르게 판단할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 5588번 별자리 찾기
# 구현
import sys
input = sys.stdin.readline

M = int(input())  # 별자리를 구성하는 별의 개수
constellation = list(tuple(map(int, input().rstrip().split())) for _ in range(M))
N = int(input())  # 사진 속 별의 개수
picture = set(tuple(map(int, input().rstrip().split())) for _ in range(N))
center_x, center_y = constellation[0]
for star in picture:
    flag = True
    star_x, star_y = star
    move_x, move_y = star_x-center_x, star_y-center_y
    for const in constellation:
        moved_star_x, moved_star_y = const[0]+move_x, const[1]+move_y
        if (moved_star_x, moved_star_y) not in picture:
            flag = False
            break
    if flag:
        print(move_x, move_y)
        break