백준 14500 / 테트로미노 / Brute Force / JAVA / 골드 5

오랜만에 백준 문제를 풀었다. Brute Force 부터 유형별로 차근차근 풀어보려 한다.

이 문제는 찐 Brute Force 문제이다. Brute Force는 하나하나 직접 다 해보는 방법을 말한다. 일반적으로 이 방법은 시간과 공간을 초과하기 때문에 만능은 아니지만.. 구현 방법이 떠오르지 않을 때는 가장 먼저 시도해 보면 좋은 방법이기도 하다.

이 문제는 5개의 테트로미노를 뒤집고 돌려서 종이에 놓았을 때 차지하는 4칸의 합을 가능한 경우 모두 구해준 뒤 가장 큰 값을 출력하면 된다. 테트로미노는 5개이지만 실제로 우리가 고려해야 하는 테트로미노는 다음과 같이 총 19개가 된다.

그리고 이 19개 각각에 대해 해당 종이(M*N)를 전부 돌면서 발생할 수 있는 모든 경우를 다 탐색해 주어야 한다. 이 경우 시간복잡도는 하나의 테트로미노당 (M*N) 이라고 볼 수 있다. 이 경우에 기준점을 하나 세우고 그 기준점을 모든 종이에서 돌면서, 종이의 범위를 벗어나지 않는 경우에 대해 테트로미노 안에 들어가는 네 개의 숫자를 더해주면 된다.

이 빨간색 점을 기준 점으로 두었다. 왼쪽의 경우 이 빨간 점이 (0, 0) 부터 (M-1, N-1)까지 돌면 그 동안 주황색 테트로미노가 지나가는 점수는 빨간 점에서 아래의 격자 포인트 만큼 계산해서 더해줄 수 있다. 예를 들어 빨간 점이 (2, 4) 이면 (2, 4), (2, 5), (3, 5), (4, 5) 이렇게 네 개의 숫자를 더해주면 되는 것이다. 기준점이 꼭 테트로미노 안에 있을 필요는 없다. 오른쪽 테트로미노의 경우는 기준점이 테트로미노 안에 없지만 탐색을 하는데 전혀 문제가 되지 않는다.

이렇게 19개의 테트로미노에 대해서 탐색을 해서 나오는 점수들의 최댓값을 출력하면 답이 된다. 시간복잡도는 O(M*N)이며 M,N < 500 이므로 시간초과 되지 않게 풀 수 있다.

JAVA로 작성한 소스 코드는 아래와 같다.