백준 [1090] 체커(Python3)

문제 링크 : https://www.acmicpc.net/problem/1090

1090번: 체커

 

좌표 다루는 문제는 경험이나 스킬이 부족해서 잘 풀지 못했는데

이번에 학회 내의 랑이집사 님의 특강을 통해 완전탐색을 통한 문제 추론 과정 설명을 듣고 거기에 맞춰 풀었다.

 

참고한 블로그 링크 : https://m.blog.naver.com/PostView.naver?blogId=gojib2002&logNo=222207408308&proxyReferer=https:%2F%2Fm.search.naver.com%2Fsearch.naver%3Fquery%3Dboj%2B1090%26where%3Dm%26sm%3Dmob_hty.idx%26qdt%3D1 

[2021.01.14] BOJ 1090 체커

지문 해석

각 점 사이의 거리를 맨해튼 거리로 계산한다.

1 ~ N개의 체커들이 최적의 비용으로 모이는 좌표가 있고, 1개 ~ N개가 모이기 위한 최적의 값들을 구하는 문제다.

 

완전 탐색

제일 먼저 완전 탐색으로 해결할 수 있는지를 본다.

1. 조합 : n개의 체커 중 m개를 고른다.

2. 탐색 : 모든 좌표에 대해 m개의 체커를 모을 때의 최적 값을 찾는다.

 

입력 개수가 최대로 들어온단 가정 하에

1번 방법은 50C1 * 50C2 * 50C3 * ... * 50C50 의 시간 복잡도가 발생해 시간 초과가 난다.

2번 방법은 100만 * 100만 개의 칸을 순회하는 것만으로도 시간 초과가 난다.

 

완전 탐색 최적화

조합 기준

1. 가까운 점끼리 묶는다.

2. m개로 묶었을 때 여기서 하나를 더 묶는다.

 

1번 방법은 가깝다라는 기준을 정하기엔 너무 모호하다.

2번 방법은 m개로 묶었을 때 최적값이 나오는 그룹이 2가지 이상인 경우

어떤 그룹에서 어떤 체커를 추가할지 정하는게 모호하다.

 

탐색 기준

1. 좌표 압축을 한다.

2. 주어진 좌표들만 본다.

 

1번 방법을 쓰기엔 각 체커들의 실제 위치가 중요하기 때문에 쓸 수 없다.

좌표 압축은 좌표 값보단 좌표간의 관계가 중요한 상황에서 쓰인다.

 

결국 남은 해결책은 2번 밖에 없다.
테스트 케이스 2번을 기준으로 x 좌표는 1, 2, 4, 9이고 y 좌표는 1만 존재하니 그 외는 보지 않는다.

 

이제 4개의 좌표를 x = {0 ~ 10} 사이의 좌표로 옮겼을 때의 총 비용을 본다.
y는 모두 1이므로 비용 계산에서 제외된다.

0 ~ 10까지 4개의 체커가 모이는데 필요한 비용

파란색으로 칠한 부분이 최적의 값이 된다.

놀라운 점을 발견할 수 있는데 특정 좌표에서 한 칸 앞으로 가면 이득을 보는 좌표와 손해를 보는 좌표가 생긴다

x 좌표가 2에서 4로 갈 때 x = 4, x = 9가 이득을 보고 x = 1, x = 2가 손해를 본다.

x 좌표가 4에서 2로 갈 때 x = 1, x = 2가 이득을 보고 x = 4, x = 9가 손해를 본다.

즉, 이득을 보는 체커와 손해를 보는 체커의 수를 맞추면 최적의 위치가 나온다.

또한, 최적의 좌표가 (x, y)라면, 이 x, y 좌표를 하나라도 가지고 있는 체커들이 존재한다.(서로 다르더라도)

 

따라서 체커들의 x, y의 쌍을 구한 다음 이 쌍마다 N개의 체커들의 맨해튼 거리를 계산한다.

총 시간 복잡도는 O(50 * 50 * 50) 이 나오게 된다.

 

코드

input = __import__('sys').stdin.readline
ans = [1e9 for i in range(64)]
V = []

def main():
    N = int(input())
    X, Y = [], []

    for _ in range(N):
        a, b = map(int, input().split())
        V.append([a, b])
        X.append(a)
        Y.append(b)

    for x in X:
        for y in Y:
            check(x, y)
    for i in range(N):
        print(ans[i], end = " ")

def check(x, y):
    temp = []
    for a, b in V:
        temp.append(abs(a - x) + abs(b - y))
    temp.sort()
    sum = 0
    for i in range(len(V)):
        sum += temp[i]
        ans[i] = min(ans[i], sum)

if __name__ == "__main__":
    main()

 

마치면서

보통 문제를 풀 때 기법 먼저 생각하고 풀었는데 이 과정에서 꼬이면 막짜서 통과하는 경우가 많았다.

그러다보니 기법이 생각나지 않거나 꼬이면 문제 감은 오는데 풀지 못하는 경우가 있었는데

완전 탐색부터 시작하는 문제 해결 방법을 익히면 지금의 문제를 해결할 수 있단 확신이 든다.

티어 2단계는 더 올릴 수 있을듯?