생각정리/코딩테스트

[JAVA 알고리즘]BAEKJOON 2527번 직사각형

생각중임 2024. 1. 30. 17:31

직사각형

문제 설명

2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다.

 

이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q로 표현된다. 단 항상 x<p, y<q 이다. 예를 들어 위 그림에 제시된 직사각형이라면 아래와 같이 표현된다.

3 2 9 8

두 개의 직사각형은 그 겹치는 부분의 특성에 따라 다음 4가지 경우로 분류될 수 있다. 

먼저 두 직사각형의 겹치는 부분이 직사각형인 경우이다. 아래 그림(a)는 공통부분이 직사각형인 경우의 3가지 예를 보여준다,

그림 (a)

또는 겹치는 부분이 아래 그림 (b)와 같이 선분이 될 수도 있고, 그림 (c)와 같이 점도 될 수 있다. 

그림 (b)

그림 (c)

마지막으로 아래 그림 (d)와 같이 공통부분 없이 두 직사각형이 완전히 분리된 경우도 있다.

그림 (d)

여러분은 두 직사각형의 겹치는 부분이 직사각형인지, 선분인지, 점인지, 아니면 전혀 없는 지를 판별해서 해당되는 코드 문자를 출력해야 한다. 

공통부분의 특성코드 문자

직사각형 a
선분 b
점 c
공통부분이 없음 d

입력

4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사각형의 좌표 값은 1이상 50,000 이하의 정수로 제한된다. 

출력

4개의 각 줄에 주어진 두 직사각형의 공통부분을 조사해서 해당하는 코드 문자를 출력파일의 첫 4개의 줄에 각각 차례대로 출력해야 한다.

제한사항

  • 없음

입출력 예

input return
3 10 50 60 100 100 200 300
45 50 600 600 400 450 500 543
11 120 120 230 50 40 60 440
35 56 67 90 67 80 500 600		 d
a
a
b

문제 분석

전제 조건으로 자동적으로 좌표값이 오름차순으로 들어온다. 순서를 그대로 사용하면된다.
조건을 4가지로 분류할 수 있는데

  1. 하나의 직사각형의 x, y가 다른 직사각형의 x, y들의 사이 값일 때와 하나의 직사각형의 x들이 다른 직사각형의 x들 사이 값일 때, 면이 겹치는 부분이 있다.
  2. 두 직사각형의 좌표값 중 하나만 일치할 경우, 선이 겹치는 부분이 있다.
  3. 두 직사각형의 좌표값 쌍이 일치할 경우, 점이 겹치는 부분이 있다.
  4. 두 직사각형의 좌표값이 하나도 일치하지 않을 경우, 완전히 분리되어 있다.

처음에는 단순 분기점들을 다 적어줘 볼까 했는데, 계산을 해보니 경우의 수가 꽤나 많아 모두 적게 되면 지저분하게 될 거 같았다.

if (coor[0] < coor[4] && coor[4] < coor[2] && coor[1] < coor[5] && coor[5] < coor[3]) {
    return true;
}
if (coor[0] < coor[4] && coor[4] < coor[2] && coor[1] < coor[7] && coor[7] < coor[3]) {
    return true;
}
if (coor[0] < coor[6] && coor[6] < coor[2] && coor[1] < coor[5] && coor[5] < coor[3]) {
    return true;
}
if (coor[0] < coor[6] && coor[6] < coor[2] && coor[1] < coor[7] && coor[7] < coor[3]) {
    return true;
}...

그러면 다르게 수를 만들어서 조건을 수행할 수 없을까를 생각해 보았다.

조건이 여러 개가 되는 1 말고 가장 적을 수 있는 3을 먼저 생각을 해봤을 때, 생각을 해보면 4가지 경우가 생긴다.

  • 빨간 네모의 작은 x와 파란 네모의 큰 x가 동일하고 빨간 네모의 큰 y와 파란 네모의 작은 y가 동일하다.
  • 빨간 네모의 큰 x와 파란 네모의 작은 x가 동일하고 빨간 네모의 큰 y와 파란 네모의 작은 y가 동일하다.
  • 빨간 네모의 큰 x와 파란 네모의 큰 x가 동일 하고 빨간 네모의 작은 y와 파란 네모의 큰 y가 동일하다.
  • 빨간 네모의 작은 x와 파란 네모의 작은 x가 동일 하고 빨간 네모의 작은 y와 파란 네모의 큰 y가 동일하다.

적용되는 값들을 비교하기 쉽게 보기 위해서 x와 y의 값들을 따로 보았다.

  • 파란 네모의 작은 x < 빨간 네모의 작은 x = 파란 네모의 큰 x < 빨간 네모의 큰 x
  • 빨간 네모의 작은 x < 파란 네모의 작은 x = 빨간 네모의 큰 x < 파란 네모의 큰 x
  • 파란 네모의 작은 x < 빨간 네모의 작은 x  = 파란 네모의 큰 x < 빨간 네모의 큰 x
  • 빨간 네모의 작은 x < 파란 네모의 작은 x = 빨간 네모의 큰 x < 파란 네모의 큰 x
  • 빨간 네모의 작은 y < 파란 네모의 작은 y = 빨간 네모의 큰 y < 파란 네모의 큰 y
  • 빨간 네모의 작은 y < 파란 네모의 작은 y = 빨간 네모의 큰 y < 파란 네모의 큰 y
  • 파란 네모의 작은 y < 빨간 네모의 작은 y = 파란 네모의 큰 y < 빨간 네모의 큰 y
  • 파란 네모의 작은 y < 빨간 네모의 작은 y = 파란 네모의 큰 y < 빨간 네모의 큰 y

경우의 수가 겹치기도 하고 하나의 반복적인 패턴이 보이기 시작했다.

작은 값 중 큰 수와 큰 값중 작은 수가 같게 반복되는 게 보였다. 그렇다면 다른 조건들에서 이와 같이 될까 한번 2번째 조건으로 실행을 해보았다.

  • 1. 빨간 네모의 작은 x < 파란 네모의 작은 x = 빨간 네모의 큰 x < 파란 네모의 큰 x
  • 1. 파란 네모의 작은 y < 빨간 네모의 작은 y < 파란 네모의 큰 y < 빨간 네모의 큰 y
  • 2. 파란 네모의 작은 x < 빨간 네모의 작은 x < 파란 네모의 큰 x < 빨간 네모의 큰 x
  • 2. 빨간 네모의 작은 y < 파란 네모의 작은 y = 빨간 네모의 큰 y < 파란 네모의 큰 y

x와 y 중 한쪽만 같아 붙어 있게 되고 다른 한쪽은 작은 값 < 큰 값으로 되면 도형이 사이에 들어와 있는 형태로 고정되는 규칙이 보인다.

이와 같이 똑같이 1번 조건을 생각을 해보면 x와 y가 둘 다 작은 값 < 큰 값이 되면 면으로 겹칠 수 있다는 걸 알 수 있었다.

 

1,2,3이 성립되지 않으면 자동적으로 4번이 성립될 것이다.

손으로 풀기

  1. for문을 이용해 4번 반복을 한다.
  2. 반복마다 입력 값을 받아 8개의 수를 차례로 배열에 넣는다.
  3. x, y, p, q값을 차례로 비교해서 작은 값 중 큰 수와 큰 값중 작은 수를 구한다.
  4. 조건에 맞는 형태로 구분하여 출력해 준다.
    • x, y 모두 작은 값 중 큰수 보다 큰 값중 작은 수가 큰 경우
    • x나 y 중 하나만 작은 값중 큰수 보다 큰 값중 작은 수가 크고 다른 한쪽은 겹을 경우
    • x, y 모두 작은 값중 큰수 보다 큰 값중 작은 수가 같은 경우
    • 모두 성립하지 않을 경우

나의 문제풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < 4; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            int[] coordinate = new int[8];
            for (int j = 0; j < 8; j++) {
                coordinate[j] = Integer.parseInt(stringTokenizer.nextToken());
            }

            // 비교하기 위해 작은 값중 큰 수와 큰 값중 작은 수를 구한다.
            int smallX = Math.max(coordinate[0], coordinate[4]);
            int smallY = Math.max(coordinate[1], coordinate[5]);
            int bigX = Math.min(coordinate[2], coordinate[6]);
            int bigY = Math.min(coordinate[3], coordinate[7]);

            //  x, y 모두 작은 값중 큰수 보다 큰 값중 작은 수가 크게 되면 사이에 있는 형태로 면이 겹친다. 
            if (smallX < bigX && smallY < bigY) {
                stringBuilder.append("a").append("\n");
            // x나 y 중 하나만 작은 값중 큰수 보다 큰 값중 작은 수가 크게 되면 한쪽만 사이에 있는 형태로 선이 겹친다.
            } else if ((smallX < bigX && smallY == bigY) || (smallX == bigX && smallY < bigY)) {
                stringBuilder.append("b").append("\n");
            // x, y 모두 작은 값중 큰수와 큰 값중 작은 수가 같게 되면 점만 겹친다.
            } else if (smallX == bigX && smallY == bigY) {
                stringBuilder.append("c").append("\n");
            // 성립되지 않으면 겹치는 곳이 없다.
            } else {
                stringBuilder.append("d").append("\n");
            }
        }
        System.out.println(stringBuilder);
    }
}

기하학 문제를 보면 실질적으로 알고리즘을 사용하지는 않아 유형을 어떻게 나눌지는 잘 모르겠다. 이제 기하학 문제를 많이 안 풀어봐서 이렇게 생각이 드는지는 잘 모르겠지만 그래도 먼가 기하학만의 재미가 있는 것 같다. 
이번 문제도 풀면서 먼가 규칙을 찾는 게 퍼즐 같아서 시간이 조금 걸렸지만 재미있게 풀었다.
다른 알고리즘이나 자료구조에 비해서 먼가 도움이 될지는 생각되지 않지만 그래도 문제해결을 하기 위해서 생각하는 방법에서 얻어가는 게 있지 않을까 싶다.

알고리즘 분류

  • 기하학
  • 많은 조건 분기

문제 출처 - https://www.acmicpc.net/problem/2527

 

2527번: 직사각형

4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사

www.acmicpc.net