[백준 14500]테트로미노

Junghyun(Alec) Park·2021년 8월 7일
0

BAEKJOON

목록 보기
5/13

테트로미노

A. 접근법

처음에 문제를 보고 DFS로 모든 경우의 수를 확인해야 겠다고 생각했습니다. (4 <= N, M <= 500이기 때문에 O(n^2)의 시간복잡도를 가지고 있다고 하면 250000, DFS의 깊이도 4밖에 되지 않음.)

문제를 푼 후 테스트 케이스를 돌렸을 때 예제 3의 답이 틀렸습니다. 이유는 보라색의 테트로미노는 DFS탐색으로 만들기 불가하였기 때문입니다.

처음부터 다시 문제를 접근해야 할까 생각했지만 문제에서 테트로미노는 다음과 같은 5가지라고 명시가 되어있고 예외 케이스는 한가지 이기 때문에 한 테트로미노에 대해서는 따로 계산해서 접근해 보았습니다.

B. 구현

Brute-force + DFS

한 칸 한 칸에 대해서 DFS기반으로 모든 테트로미노(한 케이스 제외)를 두어 놓은 칸에 쓰여 있는 수를 구하고 DFS로 구하지 못하는 한 케이스에 대해서는 따로 계산.

C. 코드

#include <iostream>
#include <vector>

using namespace std;
int T;
int N, M;
int answer;

vector<vector<int>> table;
vector<vector<int>> visit;

int i, j;

// 가려는 칸으로 이동할 수 있는지 판단
int go(int x, int y) {
    if(x >= 0 &&  x < N && y >=0 && y < M && (visit[x][y] == 0)) {
        return 1;
    }
    else {
        return 0;
    }
}

// DFS 기반 solver
void solver(int x, int y, int cnt, int point) {
    int cp = point + table[x][y];
    visit[x][y] = 1;

	// 4칸의 테트로미노 완성되고 값이 최댓값보다 크면 갱신.
    if(cnt == 4) {
        if(cp > answer)
            answer = cp;
    }
    // 4칸이 만족이 되지 않으면 다음칸으로 이동.
    else {
        if(go(x + 1, y)) {
            solver(x + 1, y, cnt + 1, cp);
        }
        if(go(x - 1, y)) {
            solver(x - 1, y, cnt + 1, cp);
        }
        if(go(x , y - 1)) {
            solver(x, y - 1, cnt + 1, cp);
        }
        if(go(x, y + 1)) {
            solver(x, y + 1, cnt + 1, cp);
        }

    }

    visit[x][y] = 0;

}

// 마지막 테트로미노(DFS로 나오지 않는 케이스)
void solver2(int x, int y) {
    int point;
    if(go(x , y - 1) && go(x + 1, y) && go(x, y + 1)) {
        point = table[x][y] + table[x][y - 1] + table[x + 1][y] + table[x][y + 1];
        if(point > answer)
            answer = point;
    }
    if(go(x  - 1, y) && go(x , y - 1) && go(x + 1, y)) {
        point = table[x][y] + table[x - 1][y] + table[x][y - 1] + table[x + 1][y];
        if(point > answer)
            answer = point;
    }
    if(go(x , y - 1) && go(x - 1, y) && go(x, y + 1)) {
        point = table[x][y] + table[x][y - 1] + table[x - 1][y] + table[x][y + 1];
        if(point > answer)
            answer = point;
    }
    if(go(x  - 1, y) && go(x , y + 1) && go(x + 1, y)) {
        point = table[x][y] + table[x - 1][y] + table[x][y + 1] + table[x + 1][y];
        if(point > answer)
            answer = point;
    }
}

int main()
{
    //scanf("%d", &T);
    T = 1;
    for(int tc = 0; tc < T; tc++) {
        answer = 0;
        scanf("%d %d", &N, &M);

        table.clear();
        visit.clear();

        table.resize(N);
        visit.resize(N);

        for(i = 0; i < N; i++)
            for(j = 0; j < M; j++) {
                int tmp;
                scanf("%d", &tmp);
                table[i].push_back(tmp);
                visit[i].push_back(0);
            }

        for(i = 0; i < N; i++) {
            for(j = 0; j < M; j++) {
                solver(i, j, 1, 0);
                solver2(i, j);
            }
        }
        printf("%d\n", answer);
    }
    return 0;
}

D. 결과

profile
박정현입니다

0개의 댓글