[백준 알고리즘] 14500번 테르토미노

문제 

1*1인 정사각형을 여러 개 이어서 붙인 도형을 폴리오미노라 하는데, 이 폴리오미노를 4개 붙인 것을 테트로미노라 한다. N*M인 종이 위에 테르토미노를 하나 놓아서 각 칸의 적혀진 수의 최대 합을 구하는 문제이다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14500)

문제 풀이

삼성 sw 역량 테스트 문제집에 있는 문제들만 풀고 있는 중인데, 이 문제는 다른 문제와 다르게 N, M의 값이 500이하라서 완전탐색이 불가능 할 것 같다는 생각이 들었다. 다 놓아서 가장 큰 값을 구하려면 500개에서 4개를 뽑아야하기때문에 방법을 좀 더 생각해봐야겠다. 우선순위 큐를 사용해서 BFS를 하면 큰 값들을 찾아갈 수 있지 않을까.. visited[i][j]를 둬서 방문하지 않은 아이가 없을 때까지 BFS를 수행하고 가장 큰 값을 큐에서 빼서 탐색을 하면 최대의 합을 구할 수 있을 것 같다.

라고 썼지만 풀다보니까 BFS로 하는 게 더 까다로울 것 같아서 DFS로 바꿨다. 그리고 완전탐색이 불가능할거같았는데 500개 중에 5개를 뽑는 경우의 수니까 그렇게 큰 연산횟수가 아니어서 가능하다고 한다. 하지만 DFS로 할 경우 ㅜ,ㅗ 와 같은 모양의 테트로미노는 탐색이 되지않는다. 따라서 이 경우에 대한 예외처리를 따로 해주어서 구현을 했다. 이런 비슷한 문제를 만나면 DFS, BFS 중에 어떤 방법이 나에게 편할지 생각해보고 어떻게 구현할 수 있을지, 예외상황이 존재하는지를 체크하고 풀면될 것 같다.

 

코드

#include<iostream>

#include<vector>

#include<queue>

#include<stdio.h>

#define max(x, y) x > y? x: y

using namespace std;

struct ptr{

int val;

int x;

int y;

};

int idx[4]={-1,0,1,0};

int idy[4]={0,1,0,-1};

class Graph{

public:

int N,M;

int cnt, result, rflag, cflag;

int P[501][501];

queue<pair<int, int>> q;

vector<pair<int, int>> s;

int visited[501][501];

Graph(){}

Graph(int n, int m){

int i, j;

N=n;

M=m;

result = -1;

}

void init()

{

int i, j;

for(i=0; i<N; i++)

for(j=0; j<M; j++)

visited[i][j]=0;

s.clear();

}

void DFS(int x, int y)

{

int size, i, j, val = 0;

visited[x][y] = 1;  //방문

s.push_back(make_pair(x, y));

if(s.size() == 4)

{

for(i=0;i<4; i++)

{

val += P[s[i].first][s[i].second];

}

result = max(val, result);

}

else{

if(s.size() == 3) //연속으로 쫙 갔는지 확인하는 것

{

if( (s[0].first  == s[1].first && s[1].first == s[2].first )&& 

( s[0].second + 2 == s[1].second + 1 && s[1].second + 1 == s[2].second ))

{

for(i=0; i<3; i++)

val += P[s[i].first][s[i].second];

if(s[1].first -1 >= 0){

val += P[s[1].first -1 ][s[1].second];

result = max(val, result);

val -= P[s[1].first -1 ][s[1].second];

}

if(s[1].first+1 < N){

val += P[s[1].first +1 ][s[1].second];

result = max(val, result);

}

}

else if( (s[0].second  == s[1].second ) && (s[1].second == s[2].second )

&& ( s[0].first + 2 == s[1].first + 1  &&  s[1].first + 1 == s[2].first ))

{

for(i=0; i<3; i++)

val += P[s[i].first][s[i].second];

if(s[1].second -1 >= 0){

val += P[s[1].first][s[1].second-1];

result = max(val, result);

val -= P[s[1].first][s[1].second-1];

}

if(s[1].second+1 < M){

val += P[s[1].first][s[1].second+1];

result = max(val, result);

}

}

}

for(i=0; i<4; i++)

{

if(x+idx[i] < 0 || x+idx[i] >= N ||

y+idy[i] < 0 || y+idy[i] >= M)

continue;

if(visited[x+idx[i]][y+idy[i]] != 1)

{

DFS(x+idx[i] , y+idy[i]);

}

}

}

visited[x][y] = 0;

s.pop_back();

}

};

int main()

{

int n, m;

int i, j;

scanf("%d %d", &n, &m);

Graph G(n,m);

for(i=0; i<n; i++)

for(j=0; j<m; j++)

scanf(" %d", &G.P[i][j]);

G.result = 0; 

for(i=0; i<n; i++){

for(j=0; j<m; j++){

G.DFS(i,j);

}

}

printf("%d\n", G.result);

return 0;

}