문제 정보
백준 ( BOJ ) 145000번 테트로미노
문제 풀이 : 패턴 파악 혹은 DFS
문제 출처 : https://www.acmicpc.net/problem/14500
문제 풀이
네 몹시 발로 그린 그림입니다..
이 문제는 다양한 풀이 법이 있겠지만, 저는 완전한 탐색쪽으 해볼까 해요.
우선 위 그림을 보시면,
빨간색 블럭이 토대가 되는 블럭입니다.
위 그림 기준, 빨간색 블럭 3개에 파란색 블럭 하나를 붙이면, 완전한 파란색 블럭(ㄱ자)
초록색 블럭을 붙이면 완전한 초록색 블럭(ㅗ자)
가 완성이 됩니다.
즉, 이런식으로 기준을 잡고, 하나씩 뼈대를 붙여 나간다는 생각으로 만들어 나가시면 됩니다.
2개짜리 블럭도 마찬가지로 하시면 됩니다.
bool checkBoundary(int y, int x) {
if (y < 0 || y >= n)
return false;
if (x< 0 || x >= m)
return false;
return true;
}
위와같이 바운더리 체크도 꼭 해주셔야 하고요.
가로 블럭, 세로 블럭을 뼈대로 각각 진행 하시면 큰 어려움 없이 진행 하실 수 있습니다.
다만 코드 길이를 줄이고자, 하나의 뼈대 블럭을 기준으로 배열로 반복문을 돌리시는게 좋을거에요.
전 2개짜리블럭, 3개짜리블럭 각각으로 돌렸지만, 원하시면 2개짜리 블럭을 검사하면서 3개짜리 블럭도 같이 검사한다면 코드가 조금은
더 짧아 질 수 있습니다.
그러나 짧은거 보단, 실수를 줄이는게 더 중요하다고 생각해서, 각각 나누어 주었습니다.
주의 사항
첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터
i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
최대값 체크
N, M 은 500개까지네요. 큰 문제는 없어 보입니다. 입력값 또한 숫자 1000을 넘지 않음으로, 최대 4000이라 int 바운더리 안에 잡히네요
최소값 체크
N, M 은 4이상이네요. 크게 고려 하지 않아도 될 거 같습니다.
개인기록
총 2회 제출. 4칸 일직선인 도형을 빼먹어서.. 더 실수 하지 않게…
소스코드
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int best = 0;
void isBest(int n) {
if (best < n)
best = n;
}
bool checkBoundary(int y, int x) {
if (y < 0 || y >= n)
return false;
if (x< 0 || x >= m)
return false;
return true;
}
// l
void stickThreeH(int y, int x, int stick, vector<vector<int>> &t) {
int yt[] = { 0,0,1,1,2,2,3};
int xt[] = { -1,1,-1,1,-1,1,0 };
for (int i = 0; i < 7; i++) {
if (checkBoundary(y + yt[i], x + xt[i]) ){
isBest(stick + t[y+yt[i]][x+xt[i]]);
}
}
}
void stickTwoH(int y, int x, int stick, vector<vector<int>> &t) {
int xa[] = { -1,1,-1,1,-1,1 };
int ya[] = { -1,-1,0,0,1,1 };
int yb[] = { 0,0,1,1,2,2 };
for (int i = 0; i < 6; i++) {
if (checkBoundary(y + ya[i], x + xa[i]) && checkBoundary(y + yb[i], x + xa[i])) {
isBest(stick + t[y+ya[i]][x+xa[i]] + t[y+yb[i]][x+xa[i]]);
}
}
}
// ㅡ
void stickThreeW(int y, int x, int stick, vector<vector<int>> &t) {
int yt[] = { -1,1,-1,1,-1,1,0 };
int xt[] = { 0,0,1,1,2,2,3 };
for (int i = 0; i < 7; i++) {
if (checkBoundary(y + yt[i], x + xt[i])) {
isBest(stick + t[y+yt[i]][x+xt[i]]);
}
}
}
void stickTwoW(int y, int x, int stick, vector<vector<int>> &t) {
int ya[] = { -1,1,-1,1,-1,1 };
int xb[] = { 0,0,1,1,2,2 };
int xa[] = { -1,-1,0,0,1,1 };
for (int i = 0; i < 6; i++) {
if (checkBoundary(y + ya[i], x + xa[i]) && checkBoundary(y + ya[i], x + xb[i])) {
isBest(stick + t[y + ya[i]][x + xa[i]] + t[y + ya[i]][x + xb[i]]);
}
}
}
int main() {
int temp;
cin >> n >> m;
vector<vector<int>> t(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> temp;
t[i][j] = temp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
temp = t[i][j] + t[i][j + 1];
stickTwoW(i, j, temp, t);
if (j != m - 2) {
stickThreeW(i, j, temp+t[i][j+2], t);
}
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n-1; i++) {
temp = t[i][j] + t[i + 1][j];
stickTwoH(i, j, temp, t);
if (i != n - 2) {
stickThreeH(i, j, temp+t[i+2][j], t);
}
}
}
cout << best;
}