[Gold 5] 14500 테트로미노

https://www.acmicpc.net/problem/14500

 

테트로미노에 존재하는 블록들은 모두 4칸인 것을 알 수 있다.

ㅗ모양을 제외하면, 모든 블록은 depth가 4인 DFS로 구할 수 있다.

따라서 ㅗ모양은 shapeN()함수로 구하고 나머지 블록은 DFS로 구할 수 있다는 것을 알 수 있다.

 

dfs의 구현은, 매번 한 칸에 대해 dfs를 시작할 때마다 visited배열을 초기화하는 것이 아닌, dfs의 특징을 살려 다음 뎁스로 넘어가기 전 visited[nextR][nextC]를 체크하고, 다시 돌아올 때 visited[nextR][nextC]를 해제하는 방법을 사용할 수 있다. 뎁스가 깊어질 때마다 방문한 칸은 체크해야 하지만, 하나의 테트로미노(한 번의 뎁스4까지 탐색)이 끝나면 다시 방문했던 칸을 방문해야 하는 일이 일어나기 때문에 다시 체크를 해제해야 하는 것이다.

이렇게 dfs는 방문했던 칸을 쉽게 되돌아갈 수 있기 때문에, bfs로는 구현이 힘들고 dfs로 하는 것이 알맞다.

즉, 어떤 노드의 유망성을 점검한 후, 유망하지 않으면 다시 부모 노드로 돌아가는 dfs에 속하는 백트래킹 알고리즘이라 할 수 있다.

 

#include <iostream>
#include <cstring>
using namespace std;

int N,M;
int graph[500][500];
int dir[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0}};
bool visited[500][500];
int answer;

bool isInside(int r, int c){
    if(r<0||r>=N||c<0||c>=M)return false;
    return true;
}
void dfs(int r, int c, int depth, int sum){
    if(depth == 3){
        answer = max(answer, sum);
        return;
    }
    for(int i = 0;i<4;i++){
        int dR = r + dir[i][0];
        int dC = c + dir[i][1];
        if(!isInside(dR,dC))continue;;
        if(visited[dR][dC])continue;
        visited[dR][dC] = true;
        dfs(dR,dC,depth + 1, sum + graph[dR][dC]);
        visited[dR][dC] = false;
    }
}
void shape1(int r, int c)
{
	int sum = 0;
	sum = graph[r][c] + graph[r][c + 1] + graph[r][c + 2] + graph[r - 1][c + 1];
	answer = max(answer, sum);
}

void shape2(int r, int c)
{
	int sum = 0;
	sum = graph[r][c] + graph[r][c + 1] + graph[r][c + 2] + graph[r + 1][c + 1];
	answer = max(answer, sum);
}

void shape3(int r, int c)
{
	int sum = 0;
	sum = graph[r][c] + graph[r + 1][c] + graph[r + 2][c] + graph[r + 1][c + 1];
	answer = max(answer, sum);
}

void shape4(int r, int c)
{
	int sum = 0;
	sum = graph[r][c] + graph[r - 1][c + 1] + graph[r][c + 1] + graph[r + 1][c + 1];
	answer = max(answer, sum);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    answer = 0;
    cin>>N>>M;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++)
            cin>>graph[i][j];
    }
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            visited[i][j] = true;
            dfs(i,j,0,graph[i][j]);
            visited[i][j] = false;
            if (i - 1 >= 0 && j + 2 < M) shape1(i, j);
			if (j + 2 < M && i + 1 < N) shape2(i, j);
			if (i + 2 < N && j + 1 < M) shape3(i, j);
			if (i + 1 < N && i - 1 >= 0 && j + 1 < M) shape4(i, j);
        }
    }
    cout<<answer;
}