BOJ 3108 로고

문제가 복잡해 보이지만 사실 간단하다.
입력으로 주어지는 직사각형을 그래프로 보면, 연결되지 않은 그래프의 개수를 세는 문제로 볼 수 있다. component의 개수를 세는 문제로 볼 수 있다.

예전에 풀 때는 좀 무식하게(?) 입력으로 주어지는 직사각형을 그래프로 나타내고 dfs를 돌려서 직사각형을 구성하는 한 점 한 점을 일일이 탐색하면서 component를 셌는데...

yukariko님(disjoint set을 이용하셨고, 나는 disjoint set을 쓰지는 않지만 직사각형끼리 연결된 것을 판별하는 것은 공통으로 필요)의 방법을 보면 component를 세긴 하지만, 직사각형을 구성하는 한 점 한 점을 일일이 탐색하는 것이 아니라 직사각형을 하나씩 본다. 그렇기 때문에 그 직사각형과 다른 직사각형이 연결되어 있는지를 판단하는 것이 매우 중요한데 문제의 조건에 보면 한 직사각형의 정보는 직사각형의 대각선의 양 끝 점인 (x1, y1), (x2, y2) 이렇게 두 점으로 주어진다.
그리고 x1<x2 and y1<y2 라는 조건이 있다. 이 조건이 성립하려면 항상 (x1, y1) 의 오른쪽 위 대각선 끝에 (x2, y2)가 위치하게 된다.

한 직사각형과 다른 직사각형이 연결되어 있는 경우는 여러가지 경우가 있다. 그래서 이것을 (x1, y2), (x2, y2)를 이용해서 구현하려면 꽤 복잡해질 것 같다. 그럼 어떻게 해야할까? yukariko님의 경우 연결된 경우를 보는 것이 아니라 연결이 되지 않는 경우를 보시는데, 연결이 되지 않는 경우가 그 경우의 수가 적고 간단하다. 그리고 그 외의 경우는 다 연결이 되는 경우이기 때문에 훨씬 간단히 구현할 수 있다.

그리고 구현할 때는 x1<x2 과 y1<y2 라는 조건을 잘 생각해서 (x1, y1), (x2, y2)를 잘 비교하면 되는데, 연결되지 않는 경우를 보면 크게 두 가지로 볼 수 있다. 한 직사각형이 다른 직사각형의 안에 포함이 되거나 혹은 아예 떨어져 있거나 이렇게 두 가지인데,
한 직사각형(A)이 다른 직사각형(B) 안에 들어간 경우는 A의 (x2, y2)가 B의 (x2, y2)보다 모두 작아야 하고, A의 (x1, y2)이 B의 (x1, y1)보다 모두 커야한다.
그리고 A와 B가 아예 떨어져 있을 경우 A가 왼쪽, B가 오른쪽에 위치한다고 하면 A의 (x2, y2)와 B의 (x1, y1)만 비교하면 된다. 왜냐하면 x1<x2, y1<y2라는 조건때문이다.

구현해 봐야겠다. WA를 받아서... 예전의 정답코드랑 비교해 봤는데 완전 거의 똑같아서 도대체 뭐가 문제일까 고민하다가 랜덤으로 데이터를 생성해서 비교해봤다...
아 결국 알아냈다. 이게 처음에는 (0, 0)에서 시작을 하기 때문에 (0, 0)에 직사각형이 있을 경우 펜을 들어 올리지 않고 바로 그려도 되므로 (최종적으로 구한 값-1) 이 정답인데,
나는 (0, 0)이라는 좌표가 들어올 경우에만 -1을 빼주는 식으로 했다. (0, 0)이라는 좌표가 들어오지 않아도 분명 (0, 0)을 지나는 직사각형은 있을 수 있는데... 이 당연한 걸 왜 생각도 못했을까.. 정말 오늘도 내가 틀릴리 없어 -> 아 내가 멍청했구나... 를 깨닫는다.

이것을 쉽게 구현하는 방법은 입력으로 받은 직사각형 외에, (x1, y1), (x2, y2)가 모두 (0, 0)인 직사각형(점)을 추가하고 최종 답에서 -1을 빼주면 된다.
왜냐하면, 입력으로 주어진 직사각형들이 (0, 0)을 지나지 않는다면 추가한 (0, 0)때문에 하나 더 count되므로 당연히 -1을 빼줘야 하고, 입력으로 주어진 직사각형들이 (0, 0)을 지난다면 count가 하나 더 되지는 않지만 -1을 빼줘야 한다.

AC를 받았다.