[Codeforces]1085C-Connect Three

1085C-Connect Three

격자무늬 상에서 좌표 3개가 주어지고 그 좌표 3개를 모두 이으려고 할 때, 방문해야 하는 격자의 수를 최소로 해야하는 문제이다. 

논리적으로 이러이러해서 이렇게 풀어야 한다기보다는, 스스로 여러가지 테스트케이스를 만들어보면서 끄적이다보니 규칙을 자연스럽게 발견하게 되는 문제라서 이런 문제는 참 설명하기가 어렵다. 일단 솔루션을 먼저 설명하고 밑에서 왜 다른 케이스는 정답이 될 수 없는지(최소가 아닌지)에 대해서 설명하겠다.

A(1,2) B(4,3)  C(5,1) 이 있다고 가정해보자.

1. 세 점 중에서 x좌표가 가장 큰 점과 가장 작은 점을 찾는다.(나는 정렬을 사용했다)

2. 그런 다음, 다시 세 점 중에서 y좌표가 중간(가장 크지도 않고, 가장 작지도 않은)점을 찾는다. 나는 이를 위해서 y좌표를 기준으로 정렬하는 cmp함수를 따로 정의했다.

3. 1번과 2번 결과의 교집합에 해당하는 부분을 먼저 색칠한다.(vector에 push_back한다. 정답은 최단거리와 최단경로를 동시에 출력해야 하기 때문이다)

4. 그런 다음, 나머지 남은 두 점(y좌표가 가장 큰 점과 작은 점)을 3번에서 그었던 기다란 선에 수선을 내리면 정답이 된다. (끝)

설명에서는 x좌표의 최대, 최소를 먼저 기준으로 잡았지만, y좌표를 기준으로 해도 상관은 없다.

그렇다면 왜 이게 정답일까? 한마디로 요약하자면 이렇게 만들어진 경로는 낭비되는 경로가 없기 때문이다. 밑에 그림으로 다시 설명하겠다.

위 그림은 y좌표를 중간에 그리지 않았을 경우의 경로이다. 보다시피 빨간색으로 색칠한 부분은 같은 열에서 두 번 사용되기 때문에 최소가 아니다.

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> Cord;
vector<Cord> buf;
bool cmp(Cord &a,Cord &b){
    return a.second<b.second;
}
int main(){
    Cord c[3];
 
    for(int i=0 ; i<3 ; i++){
        scanf("%d %d",&c[i].first,&c[i].second);
    }
 
    sort(c,c+3);
    int l=c[0].first,r=c[2].first;
 
    sort(c,c+3,cmp);
 
    for(int i=l ; i<=r ; i++){
        buf.push_back(make_pair(i,c[1].second));
    }
 
    for(int i=c[0].second ; i<c[1].second ; i++){
        buf.push_back(make_pair(c[0].first,i));
    }
 
    for(int i=c[2].second ; i>c[1].second ; i--){
        buf.push_back(make_pair(c[2].first,i));
    }
 
    printf("%d\n",buf.size());
    for(int i=0 ; i<buf.size() ; i++)
        printf("%d %d\n",buf[i].first,buf[i].second);
 
    return 0;
}