백준 2583: 영역 구하기 (Swift)

이 문제는 2차원 탐색문제이다. bfs로 간단하게 풀 수 있는 문제인데, 총 두가지 방법으로 풀어보았다.

 

1. 2차원 배열을 Bool형태로 만들어, 입력되는 직사각형에 해당하는 칸들을 true로 갱신

2. 2차원 배열을 Int형태로 만들어, 입력이 매우 많은 경우를 대비하여 누적합 방식으로 직사각형 영역을 갱신

 

배열의 가로, 세로, 직사각형 갯수가 모두 100 이하로 설정되어있어, 누적합을 사용해도 시간을 줄어드는 것을 확인할 수는 없었다.

먼저 1번. Bool타입의 2차원 배열을 사용한 방식이다.

직사각형의 대각선 양 끝 두개의 꼭짓점이 들어올 때마다, 17~19번 줄과 같이 2중 for문을 통해, 직사각형에 해당하는 칸들을 true로 갱신해준다. 이는 입력이 이 문제처럼 작은 경우에는 괜찮지만, 입력이 매우 크면, 누적합을 사용해야 시간초과를 피할 수 있을 것이다.

이번엔 2번 방식, 2차원 Int배열을 사용하고, 누적합을 사용한 방식이다.

아래와 같이, 직사각형 꼭짓점 두개가 들어오면, 가로, 세로 누적합을 거치고 직사각형 범위만 1이 더해지도록 총 네개의 점에 각 1을 더해주거나 빼준다.

ㅏ

가로, 세로 누적합을 차례로 실행해준다.

입력되는 직사각형의 갯수가 클 때는 이 방식이 훨씬 효율적일 것이다.

bfs와 출력 관련 코드는 1번 방식과 대동소이하기에 첨부하지 않았다.