hahaha   5년 전

오늘 codejam kickstart round B의 large set을 풀기위해서 맨하탄 거리를 변형해서 사용하던데, 

아래 식이 어떻게 도출되는지 모르겠습니다. ㅠ.ㅠ 

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

(x1-x2), (y1,y2)가 각각 양수 또는 음수일때 dist가 항상 abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)) 중 하나 인것은 알겠는데,

max 는(최종식은) 어디서 도출해야 할까요? 

ch1csh1n   5년 전

안녕하세요. 먼저 저는 초짜라 도움이 되는 답변 못 드려서 죄송합니다.

저도 어제 킥스타트 문제를 접했던 중 맨하탄거리 문제는 문제 자체를 이해하는데도 한참이 걸리고 있어요. 영어로는 이해했지만 알고리즘 관점에서는 어디서부터 손을 대야 할지 모르겠어요. 괜찮으시다면 문제에 대한 설명 해 주실 수 있을까요?

hahaha   5년 전

네. 요약해서 문제 해석해 드릴게요.  :) 

문제 : RxC 크기의 사각형으로 이루어진 세상이 있습니다. 각각의 사각형은 배달소(delivery office)를 포함하고 있을 수 있습니다. 배달소가 있는 사각형은 1로 배달소가 없는 사각형은 0으로 주어집니다. 각각의 사각형 위치에서 배달시간은 가장 가까운 배달소와의 거리입니다. 즉 배달소가 있는 사각형은 배달시간이 0이며, 배달소가 없는 사각형은 배달소가 있는 사각형과의 거리(맨하탄거리) 중 최소값입니다. 배달소를 최대 한개 더 지을 수 있을때, 가장 긴 배달시간을 최소화하려고 합니다. 이 때, 가장 긴 배달시간을 출력하세요.

해설:

Time limit: 15 seconds per test set.

Test Case 1<=T <=100

Test Set 1 ( 1<=R<=10, 1<=C<=10)

임의의 배달소에서 다른 사각형까지의 배달시간은 BFS로 구할 수 있습니다. 배달시간이 맨하탄 거리(두 지점이 (r1,c1), (r2,c2) 일 때, 맨하탄거리는 |r1 - r2| + |c1 - c2|)이기 때문에 배달소에서 시작하여서 상하좌우 인접한 사각형을 방문할수 있고, 다시 방문한 사각형에서 상하좌우로 인접한 사각형들 중 방문하지 않은 사각형들을 방문하는 식으로 진행할 수 있습니다. (boj에 있는 문제로 유명하고 유사한 문제는 "토마토"가 있어요. 7569,7576번) 이는 queue에 배달시간 t에 방문한 노드들이 들어있다고 가정했을 때, 배달시간 t+1에 방문하는 사각형들을 찾을 수 있고, 즉 모든 지점을 방문했을 때가 최대 배달시간이 됩니다. 이 때 시간복잡도는 O(RC)입니다. 배달소가 여러개 있을 때, 배달시간 0에 해당되는 사각형이 여러개있는것으로 bfs를 시작할때 queue에 모든 배달소를 먼저 넣고 시작하면되므로 역시 시간복잡도는 동일하게 O(RC)입니다. 그런데, 문제에서 배달소를 한개 더 지을 수 있다고 했기때문에, 배달소를 곳곳에 설치했을때, 최대 배달시간의 최솟값이 얼마인지 확인해야합니다. 이 때, 가능한 설치장소는 RxC개이므로 RxC번 BFS를 진행하게 된다면, O((RC)^2 * T)으로 문제를 해결 할 수 있습니다.

Test Set 2 ( 1<=R<=250, 1<=C<=250)

그런데 위와 같은 전탐색으로는 제한시간내에 test set2를 풀 수가 없습니다. 따라서 다르게 접근해야 합니다.

최대 배달시간이 K보다 작거나 같다를 만족하면 YES, 만족하지 않다면 NO를 출력하는 문제라고 생각해 봅시다. 만약 임의의 수 K에 대하여 정답이 YES라면 [K+1, infinity]범위에서도 문제를 만족합니다. 만약 정답이 NO라면 [0,K-1]에서도 NO에 해당합니다. 원래 우리가 찾는 정답은 최소 K의 값입니다. 따라서 이 문제는 K를 binary search로 구하고 만족하는 K인지 확인하는 sub problem을 해결하는 문제로 바뀝니다! 

문제 해설의 따르면 맨하탄 거리는 다음과 같은 식으로 변형할 수 있습니다. (왜 이렇게 가능한지는 저도 아직.. ㅠㅠ)

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

(x2, y2)에 해당하는 위치에 배달소를 세운다고 가정해 봅시다. 그렇다면 최대 배달시간은, 원래 존재했던 배달소와의 최소 거리가 K보다 큰 사각형들과 (x2,y2)위치와의 거리중 최대값이 됩니다. (x2,y2)가 고정되어있을 때, x2+y2, x2-y2는 고정된값이므로 (x1,y1)의 값에 따라 최대 배달 시간이 결정됩니다. 즉 x1+y1, x1-y1에 해당하는 최대 또는 최소값에 따라 최대배달시간이 결정됩니다. 이 x1+y1, x1-y1은 미리 구할 수 있는 값이기에, x1+y1, x1-y1의 최대 최소값도 바로 구할 수 있습니다. 즉 sub problem을 해결하는 시간은 O(RC)가 됩니다. 그리고 K를 정하는 binary search의 시간복잡도는 O(log(R+C))이기때문에, 이렇게 문제를 풀면 O(RClog(R+C))가 됩니다.

ch1csh1n   4년 전

정말 이렇게 친절하고 자세하게 설명해주셨다니,, 도움이 못되어 더욱 죄송한 마음 뿐이네요. 하하하님 덕분에 문제 잘 이해했습니다! 너무 감사드려요. 하하님께서도 궁금하셨던 점 꼭 해결하시길 바랄게요 감사합니다.

xman   3년 전

댓글을 작성하려면 로그인해야 합니다.