백준 14500 - 테트로미노

백준 14500 문제 바로가기

풀이

(문제 설명은 링크를 참고하자)

이 문제에서는 5종류의 테트로미노(정사각형 4개를 이어 붙인 폴리오미노)가 있다.

테트로미노는 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

이전에 풀었던 문제중에 특정 길이(또는 깊이)만큼 DFS를 수행하는 문제가 있어서 DFS로 접근해도 되겠다는 생각을 했다.

예를 들어, 임의의 위치(r, c)에서 시작하여 4방향(상,우,하,좌)으로 뻗어나가면서 깊이가 4가 될 때까지 중복 방문을 허용하지 않고 DFS를 수행하면, (ㅏ ㅜ ㅓ ㅗ) 모양을 제외한 나머지 4종류의 테트로미노를 대칭 및 회전한 결과를 만들 수 있다.

이제 ㅏ ㅜ ㅓ ㅗ 모양을 검사해야 하는데, ㅜ 모양을 대칭하면, (ㅏ ㅜ ㅓ ㅗ)와 같은 모양이 될 수 있고, 이러한 모양들은 임의의 위치(r, c)에서 [상우하, 우하좌, 하좌상, 좌상우] 위치를 검사하면 얻을 수 있다.

4방향(상,우,하,좌)의 인덱스가 {0, 1, 2, 3}이므로, [012(상우하),123(우하좌),230(하좌상),301(좌상우)]을 검사하면 되는데, 이 부분은 코드로 나타내면 아래와 같다.

const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 };

...

for (int d = 0; d != 4; ++d) {
	int tSum = sum;
	for (int i = 0; i < 3; ++i) {
		int nr = r + dr[(d + i) % 4];
		int nc = c + dc[(d + i) % 4];

		// 모양을 못만들면 더 진행할 필요가 없음. break;
		if (nr < 0 || nc < 0 || nr >= N || nc >= M) break;
		tSum += m[nr][nc];
	}
	if (ans < tSum) {
		ans = tSum;
	}
}

소스 코드

#include <iostream>
using namespace std;

int N;//세로
int M;//가로

int m[500][500];
int ans;


const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 };
bool visited[500][500];
void dfs(int r, int c, int len, int sum) {
    if (len == 4) {
        //m[r][c] = 1;
        //for (int i = 0; i < 10; ++i) {
        //    for (int j = 0; j < 10; ++j) {
        //        cout << m[i][j];
        //    }
        //    cout << '\n';
        //}
        //cout << '\n';
        //m[r][c] = 0;

        if (ans < sum) {
            ans = sum;
        }

        return;
    }

    //m[r][c] = 1;
    visited[r][c] = true;
    for (int d = 0; d != 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc]) continue;
        dfs(nr, nc, len + 1, sum + m[nr][nc]);
    }
    visited[r][c] = false;
    //m[r][c] = 0;
}

// ㅏ ㅜ ㅓ ㅗ
void search(int r, int c, const int sum) {
    for (int d = 0; d != 4; ++d) {
        int tSum = sum;
        for (int i = 0; i < 3; ++i) {
            int nr = r + dr[(d + i) % 4];
            int nc = c + dc[(d + i) % 4];

            // 모양을 못만들면 더 진행할 필요가 없음. break;
            if (nr < 0 || nc < 0 || nr >= N || nc >= M) break;
            tSum += m[nr][nc];
        }
        if (ans < tSum) {
            ans = tSum;
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);

    cin >> N >> M;

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            cin >> m[r][c];
        }
    }

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            dfs(r, c, 1, m[r][c]);
            search(r, c, m[r][c]);
        }
    }

    cout << ans;
    return 0;
}