백준 14500번
오늘 풀어본 문제는 백준의 14500번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 $N$×$M$인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
입력
첫째 줄에 종이의 세로 크기 $N$과 가로 크기 $M$이 주어진다. ($4 \leq N, M \leq 500$)
둘째 줄부터 $N$개의 줄에 종이에 쓰여 있는 수가 주어진다. $i$번째 줄의 $j$번째 수는 위에서부터 $i$번째 칸, 왼쪽에서부터 $j$번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 $1,000$을 넘지 않는 자연수이다.
출력
첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
풀이과정
첫 번째 시도
처음에 문제를 봤을 때, 제한 시간이 2초인 것을 보고, 브루트 포스 기법을 써도 된다는 것 정도는 짐작할 수 있었다. 2초라고 해서 무조건 브루트 포스 기법을 쓸 수 있는 것은 아니지만, 가능한 칸의 개수가 비교적 적은 편이기 때문에 가능할 것이라고 생각했다.
브루트 포스 기법을 쓰는 것은 좋았는데, 처음에 떠올린 방법은 가능한 모든 도형을 ‘틀’ 처럼 만들어서 모든 칸에다가 틀을 찍어서 계산하는 방식을 적용하여 최대값을 찾아내려 하였따. 그런데 구현할 방법이 딱히 떠오르지 않아 다른 방법을 사용하였다.
각 칸에서 DFS를 활용하여 최대 4칸까지 탐색하는 방법하도록 하여 값을 계산하고 비교하는 방식을 생각해보았다. 이 경우에, T자 모양 블럭은 그런 방식으로 찾을 수 있는 도형이 아니었기 때문에, 탐색 중간에 예외를 두어 미리 계산해두고 다른 탐색 결과값과 비교하도록 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int evaluateGrid(int searchDepth, int(*paper)[501], int height, int width, pair<int, int> gridPosition, pair<int, int> prevGridPosition, pair<int, int> prevOfPrevGridPosition);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int height, width, tempValue;
int paper[501][501] = { 0, };
int maximum = 0;
cin >> height >> width;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
cin >> tempValue;
paper[i][j] = tempValue;
}
}
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int tempValue = evaluateGrid(1, paper, height, width, { i , j }, { -100, -100 }, { -200, -200 });
if (maximum < tempValue) {
maximum = tempValue;
}
}
}
cout << maximum;
return 0;
}
int evaluateGrid(int searchDepth, int(*paper)[501], int height, int width, pair<int, int> gridPosition, pair<int, int> prevGridPosition, pair<int, int> prevOfPrevGridPosition) {
int result = 0;
int up, down, left, right;
if (gridPosition.first < 0 || gridPosition.first > height - 1 || gridPosition.second < 0 || gridPosition.second > width - 1) {
return 0;
}
else if (gridPosition.first == prevOfPrevGridPosition.first && gridPosition.second == prevOfPrevGridPosition.second) {
return 0;
}
else if (searchDepth < 4) {
if (searchDepth == 2) {
if (prevGridPosition.first == gridPosition.first) {
if (gridPosition.first > 0 && gridPosition.first < height - 1) {
result = (paper[gridPosition.first - 1][gridPosition.second] + paper[gridPosition.first + 1][gridPosition.second]);
}
}
else if (prevGridPosition.second == gridPosition.second) {
if (gridPosition.second > 0 && gridPosition.second < width - 1) {
result = (paper[gridPosition.first][gridPosition.second - 1] + paper[gridPosition.first][gridPosition.second + 1]);
}
}
}
up = evaluateGrid(searchDepth + 1, paper, height, width, { gridPosition.first - 1, gridPosition.second }, gridPosition, prevGridPosition);
down = evaluateGrid(searchDepth + 1, paper, height, width, { gridPosition.first + 1, gridPosition.second }, gridPosition, prevGridPosition);
left = evaluateGrid(searchDepth + 1, paper, height, width, { gridPosition.first, gridPosition.second - 1 }, gridPosition, prevGridPosition);
right = evaluateGrid(searchDepth + 1, paper, height, width, { gridPosition.first, gridPosition.second + 1 }, gridPosition, prevGridPosition);
result = max({ result, up, down, left, right });
return (result + paper[gridPosition.first][gridPosition.second]);
}
else {
return paper[gridPosition.first][gridPosition.second];
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
제출은 한 번에 성공했지만, 실제로는 엄청나게 오랜 시간이 걸린 문제였다.
아침 일찍이 부터 풀기 시작한 문제이지만, 제출은 자정까지 1시간도 안 남은 시간에 하게되었다. 물론 하루종일 PS만 붙들고 있었던 것은 아니긴 하지만, 꽤 오래 걸렸다는 사실이 좀 충격적이었다.
복잡한 알고리즘을 알아야 했던 것도 아니고, 새로운 자료구조 같은 것을 사용해야 하는 문제도 아니었다. 다만, 탐색을 수행하는 evaluateGrid 함수를 만드는 것이 생각보다 오래 걸렸다.
제출을 하기 전에 우선 제공된 테스트 케이스는 모두 돌려본다. 그런데 초기의 코드들은 모든 테스트 케이스에서 이상한 결과를 제공했다. 차라리 프로그램이 중단되는 문제였다면, 디버거로 잘못된 쉽게 찾아낼 수 있었겠지만, 프로그램 자체는 또 제대로 작동했기 때문에 굉장히 골치가 아픈 문제였다.
거의 다 풀릴 시기에는 정신력의 거의 다 깎여나간 상태여서 매개 변수 이름도 어이없게 지었다. 어떻게 변수 이름이 prevOfPrevGridPosition 일 수 있겠는가? 애초에 이런 매개 변수를 만들지 않고, 더 깔끔하게 문제를 해결하는 방법이 있을 것이라고 생각한다. 하지만 빨리 제출하고 자유로워지고 싶다는 마음에 대충하게 된 것 같다.
PS를 열심히 하는 것은 좋지만, 오늘처럼 대충대충 해먹으려는 심보는 고쳐야할 것 같다. 프로그래밍을 하다보면 고되고 귀찮은 작업들도 해야 하기 마련인데, 고작 CLASS 3 수준의 문제에 이 정도의 시간을 쏟고, 또 정신력이 심하게 깎여나갔다는 사실은 다소 절망적으로 느껴진다. 앞으로는 마음을 굳게 먹고 임해야겠다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/14500