[C/C++] 백준 14500번 - 테트로미노, 삼성 코딩 테스트 문제를 두 가지 방법으로 풀어보자

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

14500번: 테트로미노

매우 간단한 문제입니다.

 

1. 문제요약

테트로미노를 놓아서 나올 수 있는 최대값을 구하자

 

2. 생각의 흐름

그냥 다 하면 되겠는데?

 

3. 그래서 나온 코드

이후 개선된 코드가 있습니다.

#include <iostream>
using namespace std;
int map[555][555];
int n, k;
void input();
void solve();
int poly(int a, int b);
void except();
int main(){
    input();
    solve();
}
void input(){
    scanf("%d", &n);
    scanf("%d", &k);
    for(int j = 1; j <= n; j++){
        for(int i = 1; i <= k; i++) {
            scanf("%d", &map[j][i]);
        }
    }
}
void solve(){
    int ans = 0;
    for(int j = 1; j <= n; j++){
        for(int i = 1; i <= k; i++) {
            ans = max(ans, poly(j, i));
        }
    }
    printf("%d", ans);
}
int poly(int a, int b){ // 단순히 모든 테트로미노를 체크해본다
    int res = 0;
    if (b + 3 <= k) res = max(res, map[a][b] + map[a][b + 1] + map[a][b + 2] + map[a][b + 3]);
    if (a + 3 <= n) res = max(res, map[a][b] + map[a + 1][b] + map[a + 2][b] + map[a + 3][b]);
    
    if (a + 1 <= n and b + 1 <= k) res = max(res, map[a][b] + map[a][b + 1] + map[a + 1][b] + map[a + 1][b + 1]);
    
    if (a + 2 <= n and b + 1 <= k) res = max(res, map[a][b] + map[a + 1][b] + map[a + 2][b] + map[a][b + 1]);
    if (a + 2 <= n and b - 1 >= 1) res = max(res, map[a][b] + map[a + 1][b] + map[a + 2][b] + map[a][b - 1]);
    if (a - 1 >= 1 and b + 2 <= k) res = max(res, map[a][b] + map[a][b + 1] + map[a][b + 2] + map[a - 1][b]);
    if (a + 1 <= n and b + 2 <= k) res = max(res, map[a][b] + map[a][b + 1] + map[a][b + 2] + map[a + 1][b]);
    if (a - 2 >= 1 and b - 1 >= 1) res = max(res, map[a][b] + map[a - 1][b] + map[a - 2][b] + map[a][b - 1]);
    if (a - 2 >= 1 and b + 1 <= k) res = max(res, map[a][b] + map[a - 1][b] + map[a - 2][b] + map[a][b + 1]);
    if (a + 1 <= n and b - 2 >= 1) res = max(res, map[a][b] + map[a][b - 1] + map[a][b - 2] + map[a + 1][b]);
    if (a - 1 >= 1 and b - 2 >= 1) res = max(res, map[a][b] + map[a][b - 1] + map[a][b - 2] + map[a - 1][b]);
 
    
    if (a - 1 >= 1 and a + 1 <= n and b - 1 >= 1) res = max(res, map[a][b] + map[a - 1][b] + map[a][b - 1] + map[a + 1][b - 1]);
    if (a - 1 >= 1 and a + 1 <= n and b - 1 >= 1) res = max(res, map[a][b] + map[a + 1][b] + map[a][b - 1] + map[a - 1][b - 1]);
    if (a + 1 <= n and b + 1 <= k and b - 1 >= 1) res = max(res, map[a][b] + map[a + 1][b] + map[a][b + 1] + map[a + 1][b - 1]);
    if (a + 1 <= n and b + 1 <= k and b - 1 >= 1) res = max(res, map[a][b] + map[a + 1][b] + map[a][b - 1] + map[a + 1][b + 1]);
    
    if (a - 1 >= 1 and a + 1 <= n and b + 1 <= k) res = max(res, map[a][b] + map[a + 1][b] + map[a - 1][b] + map[a][b + 1]);
    if (a - 1 >= 1 and a + 1 <= n and b - 1 >= 1) res = max(res, map[a][b] + map[a + 1][b] + map[a - 1][b] + map[a][b - 1]);
    if (b - 1 >= 1 and b + 1 <= k and a - 1 >= 1) res = max(res, map[a][b] + map[a - 1][b] + map[a][b + 1] + map[a][b - 1]);
    if (b - 1 >= 1 and b + 1 <= k and a + 1 <= n) res = max(res, map[a][b] + map[a + 1][b] + map[a][b + 1] + map[a][b - 1]);
    
    return res;
}

그래서 나온 코드 입니다. 모든 점을 방문하면서 모든 테트로미노의 모양을 넣으면 답이 나오죠.

눈여겨 볼 점은, i = 1, j = 1 에서 시작한 것입니다. 그렇게 하면 범위를 넘어가는 것이 방지되죠

 

---

4. 그런데 이렇게 풀 순 없지요

도형에 정사각형 개수가 더 많다면 구하기 힘든 방법입니다. 경우의 수가 기하급수적으로 늘기 때문이죠.

출제자가 의도한 대로 풀어봅시다.

 

5. 생각의 흐름

한 점에서 시작해서 상하좌우에 있는 점으로 이동하면서 총 4개의 점을 방문하면, 모든 테트로미노를 확인하는 걸까?

Snake game

DFS를 해서 이 뱀게임 모양처럼 하면 될꺼 같은데!

#include <iostream>
using namespace std;
int n, m, ans;
int paper[555][555];
int visited[555][555];
int dy[4] = {1, 0, -1, 0}; // 상하좌우를 표시한다.
int dx[4] = {0, 1, 0, -1};
void dfs(int y, int x, int cnt, int val) {
    if (cnt == 4) ans = ans < val ? val : ans;
    else {
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i]; int nx = x + dx[i]; // y, x의 상하좌우에 있는 값
            if (ny < 1 or ny > n or nx < 1 or nx > m) continue; // 범위제한
            if (visited[ny][nx]) continue; // 이미 방문한 곳이면 방문하지 않는다
            visited[ny][nx]++; // 방문한 곳을 표시
            dfs(ny, nx, cnt + 1, val + paper[ny][nx]); // 더 깊숙이가거나, 테트로미노임을 확인한다
            visited[ny][nx]--; // 표시를 삭제
        }
    }
}
int main() {
    ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> paper[i][j];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            visited[i][j]++; // 방문한 곳을 표시
            dfs(i, j, 1, paper[i][j]); // 테트로미노
            visited[i][j]--; // 표시를 삭제
        }
    } 
    cout << ans;
}

하며 나온 코드죠. 이 코드는 당연히 실패했습니다.

DFS로 가능한 테트로미노

오른쪽 밑 보라색 테트로미노는 DFS로 나올 수 없습니다. DFS는 계속 깊어지기만 해서 중간에 혹처럼 튀어나온 블록을 확인할 수 없죠.

 

그렇다면 DFS로는 보라색 테트로미노를 제외하곤 다 알 수 있으니

#include <iostream>
using namespace std;
int n, m, ans;
int paper[555][555];
int visited[555][555];
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
void dfs(int y, int x, int cnt, int val) {
    if (cnt == 4) ans = ans < val ? val : ans;
    else {
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i]; int nx = x + dx[i];
            if (ny < 1 or ny > n or nx < 1 or nx > m) continue;
            if (visited[ny][nx]) continue;
            visited[ny][nx]++;
            dfs(ny, nx, cnt + 1, val + paper[ny][nx]);
            visited[ny][nx]--;
        }
    }
}
int main() {
    ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> paper[i][j];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            visited[i][j]++;
            dfs(i, j, 1, paper[i][j]);
            visited[i][j]--;
        }
    } 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int t = paper[i][j]; // 보라색 테트로미노의 가운데를 표시한다
            int mini = 1001;
            for (int k = 0; k < 4; k++) {
                mini = mini < paper[i + dy[k]][j + dx[k]] ? mini : paper[i + dy[k]][j + dx[k]]; // 가운데 점의 상하좌우에 있는 값 중에 최소의 값을 나타낸다
                t += paper[i + dy[k]][j + dx[k]]; // 상하좌우에 있는 값을 모두 더한다. 그러면 십자가 모양처럼 되니 테트로미노가 아니다
            }
            ans = ans < t - mini ? t - mini : ans; // 상하좌우에 있는 값 중 최소 값을 제거한다. 그러면 보라색 테트로미노의 모양이 된다
        }
    } 
    cout << ans;
    return 0;
}
 

와 같이 구현해 준다면 통과할 수 있습니다.

DFS + 완전탐색