[KOI 기출] 두 박스 (2018 전국 중1)

이 문제는 알고리즘 문제는 아니지만, 그냥 풀면 복잡한 문제를 얼마나 쉽게 단순화할 수 있는지를 잘 보여주는 문제다.

 

문제 보기

---

정올 3232번, 백준 15973번

 

접근 방법

---

1. 노가다

노가다로 찾아도 Line은 "비교적" 쉽게 찾을 수 있다. 아마 조건문을 한 15개쯤 쓰면 Line과 Point는 판별할 수 있다. Line을 찾으려면 공유하는 x 또는 y좌표가 있는지 찾은 후에, 내접하는지, 외접하는지, 아니면 만나지 않는지만 따져주면 된다. x 좌표 하나만을 공유하는 경우는 다음과 같은 것들이 있다. (물론 왼쪽 변의 위치 관계도 고려하고, 저것들은 선대칭한 케이스들도 고려해야 하지만, 대표적으로는 저렇게 나타낼 수 있다.) 이중 마지막 2개가 Line이다. Point는 비슷하게 x좌표 하나와 y좌표 하나가 겹치는 경우에 대해 따져주면 된다. 이렇게 하면 최소한 1번 부분문제는 맞힐 수 있다.

그러나 이런 방법으로 Face와 Null까지 구분하려면 조건문이 굉장히 많아야 한다. 실제로 이렇게 구현해서 100점을 맞은 친구를 보긴 했다. 2시간 가까이 걸리긴 했지만... (실전에서는 2~4번을 풀 자신이 없다면 이렇게 해서라도 1번을 100점을 맞는 게 훨씬 낫다.)

그보다는 경우의 수를 얼마나 효율적으로 나누느냐가 중요하다.

 

2. 축 쪼개기

이 문제는 x축과 y축을 따로 생각해주면 편하다. 아까 전 그림의 x성분의 위치관계만 생각해보자. 즉 그림들을 화살표 방향에서 바라봐보자.

위 그림의 위쪽 3개 경우가 1번에 해당하고, 아래쪽 3개가 2번에 해당한다.

마찬가지로 x성분을 무시한 y성분의 위치관계도 그려보자. 위의 6개짜리 그림에서 1열이 a, 2열이 b, 3열이 c이다.

위의 6개짜리 그림을 각 축의 위치관계로 표시해보면 각각 1a, 1b, 1c, 2a, 2b, 2c이다.

이제 Line이기 위한 조건을 다시 생각해보자. 적어도 한 축에 대해서는 2처럼 외접해야 하고, 나머지 축에 대해서는 b나 c처럼 겹치는 부분이 존재해야 한다.

Point를 가로, 세로로 분해하면 언제나 x성분과 y성분이 각각 한 점에서 만나는 걸 확인할 수 있다.

Line을 가로, 세로로 분해하면 한 축에 대해서는 선분이 한 점에서 만나고, 한 축에 대해서는 겹치는 부분이 존재한다.

Face는 x성분과 y성분 모두 겹친다.

Null은 적어도 한 축에 대해서는 겹치지 않는다.

정리하면 다음과 같다.

그러면 이제 사각형별로 x성분과 y성분을 나눠주고, 성분별로 구간(선분)을 비교하는 함수를 만들고, 이 함수의 리턴값에 따라 위 표와 같이 경우를 나눠주면 된다.

다음과 같이 구간을 저장하는 struct line과 두 구간의 위치관계를 비교하는 inter 함수를 만들어 줬다.

struct line {
  int s, e; // 시작 좌표와 끝 좌표
};

// 두 구간이 겹치면 2, 한 점에서 접하면 1, 안 겹치면 0 리턴
int inter(line a, line b) {
  // ???
}

int main() {
  // ... (입력을 바탕으로 직사각형의 x성분과 y성분을 나누어 x1, x2, y1, y2에 저장한다.)
  int ix = inter(x1, x2), iy = inter(y1, y2);
  if (ix == 2 && iy == 2) printf("FACE");
  else if (ix == 1 && iy == 2 || ix == 2 && iy == 1) printf("LINE");
  else if (ix == 1 && iy == 1) printf("POINT");
  else printf("NULL");
}

 

3. 선분 위치관계 구하기

이제 inter 함수만 구현하면 되는데 이것도 생각보다 어려울 수 있다. 그러나 한 구간의 시작점이 다른 구간의 시작점보다 작다는 게 보장되면 생각하기 훨씬 편해진다. a.s <= b.s가 보장되면 a.e와 b.s의 위치만 비교해주면 된다.

int inter(line a, line b) {
  // a의 시작점이 b보다 크면 swap
  if (a.s > b.s) {
    line tmp = a;
    a = b;
    b = tmp;
  }
  if (a.e < b.s) return 0;
  else if (a.e == b.s) return 1;
  else return 2;
}

 

코드

---

#include <stdio.h>

struct line {
  int s, e;
};

int inter(line a, line b) {
  if (a.s > b.s) {
    line tmp = a;
    a = b;
    b = tmp;
  }
  if (a.e < b.s) return 0;
  else if (a.e == b.s) return 1;
  else return 2;
}

int main() {
  line x1, y1;
  line x2, y2;

  scanf("%d%d%d%d", &x1.s, &y1.s, &x1.e, &y1.e);
  scanf("%d%d%d%d", &x2.s, &y2.s, &x2.e, &y2.e);
  int ix = inter(x1, x2), iy = inter(y1, y2);
  if (ix == 2 && iy == 2) printf("FACE");
  else if (ix == 1 && iy == 2 || ix == 2 && iy == 1) printf("LINE");
  else if (ix == 1 && iy == 1) printf("POINT");
  else printf("NULL");
}