영역구하기
title: “2583 - 영역구하기”
date: “2019-02-12”
category: “algorithm”
문제요약
- 전체 모눈종이의 크기 M, N과 모눈종이에 올라갈 사각형의 크기 K가 주어진다.
- K개 만큼 사각형이 주어진다.
- 모눈종이에 사각형을 올렸을 때 모눈종이가 몇개의 영역으로 나누어 지는지 출력해라
접근법
이문제를 쉽게 푸는 방법은 단지번호붙이기(2667) 번의 형태로 변경해서 푸는 것이다. 먼저 주어진 M X N의 크기의 모눈종이를 만든다. 이때 모눈종이 각 칸의 값을 1로 초기화한다. 이후 K개 만큼의 직사각형을 입력받고, 직사각형에 의해 가려지는 부분의 값을 0으로 바꾼다.
문제에서 주어진 입력을 예제로 살펴보면 문제에서는 아래와 같은 입력을 예제로 줬다.
| 5 | 7 | 3 | |
|---|---|---|---|
| 0 | 2 | 4 | 4 |
| 1 | 1 | 2 | 5 |
| 4 | 0 | 6 | 2 |
먼저 모눈종이의 크기가 5 X 7이기 때문에 초기 모눈종이는 아래와 같다.
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
초기 모눈종이에서 직사각형으로 가려지는 부분을 0으로 바꾼 뒤 다시한번 모눈종이를 확인해보면 아래와 같이 나타난다.
| 1 | 0 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 |
위 모눈종이 값을 보면 단지 번호 붙이기 문제와 똑같은 배열이 되었음을 확인할 수 있다. 이제 위의 모눈종이를 단지 번호 붙이기 문제에 사용했던 BFS와 같은 방법을 이용하여 풀수 있다. 단지 번호 붙이기와 관련된 게시글은 여기에서 확인할 수 있다.
모눈종이에서 직사각형에 의해 가려진 부분을 0으로 바꿀 때 주의해야할 부분은 직사각형의 정보로 주어지는 내용이 좌표값이라는 점이다. 즉 칸에대한 정보가 아니라 각 칸의 꼭지점에 대한 정보가 되는 것이다. 따라서 직사각형에 해당하는 칸을 찾아서 0으로 바꿀때는 우측 상단에 해당하는 좌표를 각각 1씩 빼줌으로써 칸에대한 정보로 변경하여야 한다. 또한 (0, 0)이 모눈종이의 좌측 상단에 해당하는 꼭지점이 아니라 좌측 하단에 해당하는 꼭지점이며, 위의 예제에서 우측 상단에 해당하는 꼭지점이 (5, 7)이 된다. openGL에서 사용하는 좌표계와 같다.
댓글남기기