14500번 테트로미노

두 번째 풀이 방법은 신선하여 첨부하였다.

삼성 SW 역량 테스트 기출 문제이다.

방문 여부(visit)를 잘 생각해줘야한다. 

방문 여부를 생각하지 못 하여(다음 테트로미노를 위한 재사용), 다른 분의 코드를 참고하였다.

이 문제를 통해 기억해야할 것

1. 36, 40, 92, 98 번 째 줄은 반드시 써줘야한다. 

그래야 다음 모양의 테트로미노를 계산할 때, 다시 한 번 정사각형 한 칸의 크기를 사용할 수 있다.

2. otherShape 함수는 DFS로는 탐색할 수 없는 모양(ㅗ)을 위해 따로 만들어준 함수다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int map[501][501] = { 0, };
 
bool visit[501][501] = { false, };
 
int N = 0, M = 0;
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int result = 0;
 
int DFS(int r, int c, int Cnt)
{
    if (Cnt == 4) return map[r][c];
 
    int MAX = 0;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (0 <= y && y < N && 0 <= x && x < M && !visit[y][x])
        {
            visit[y][x] = true;
 
            MAX = max(MAX, map[r][c] + DFS(y, x, Cnt + 1));
 
            visit[y][x] = false;
        }
    }
 
    return MAX;
}
 
int otherShape(int y, int x)
{
    int ret = 0;
 
    if (y - 1 >= 0 && x - 1 >= 0 && x + 1 < M) // ㅗ
    {
        ret = max(ret, map[y - 1][x] + map[y][x - 1] + map[y][x] + map[y][x + 1]);
    }
 
    if (y - 1 >= 0 && y + 1 < N && x + 1 < M) // ㅏ
    {
        ret = max(ret, map[y - 1][x] + map[y][x] + map[y + 1][x] + map[y][x + 1]);
    }
 
    if (y + 1 < N && x - 1 >= 0 && x + 1 < M) // ㅜ
    {
        ret = max(ret, map[y + 1][x] + map[y][x - 1] + map[y][x + 1] + map[y][x]);
    }
 
    if (y - 1 >= 0 && y + 1 < N && x - 1 >= 0) // ㅓ
    {
        ret = max(ret, map[y - 1][x] + map[y][x] + map[y + 1][x] + map[y][x - 1]);
    }
 
    return ret;
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (!visit[i][j])
            {
                visit[i][j] = true;
 
                result = max(result, DFS(i, j, 1));
 
                result = max(result, otherShape(i, j));
 
                visit[i][j] = false;
            }
        }
    }
 
    printf("%d\n", result);
 
    return 0;
}

아래는 신박한 풀이 방법이다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 505
#define Min -5000
 
int R, C, m[Max][Max];
 
vector<vector<vector<int> > > v = {
    { // 0
        { 1, 1, 1, 1 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 1
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 }
    },
    { // 2
        { 1, 1, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 3
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 4
        { 1, 1, 1, 0 },
        { 1, 0, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 5
        { 1, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 6
        { 0, 0, 1, 0 },
        { 1, 1, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 7
        { 0, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 8
        { 1, 0, 0, 0 },
        { 1, 1, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 9
        { 1, 1, 0, 0 },
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 10
        { 1, 1, 1, 0 },
        { 0, 0, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 11
        { 1, 0, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 12
        { 0, 1, 1, 0 },
        { 1, 1, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 13
        { 0, 1, 0, 0 },
        { 1, 1, 0, 0 },
        { 1, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 14
        { 1, 1, 0, 0 },
        { 0, 1, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 15
        { 1, 1, 1, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 16
        { 0, 1, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 17
        { 0, 1, 0, 0 },
        { 1, 1, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 18
        { 1, 0, 0, 0 },
        { 1, 1, 0, 0 },
        { 1, 0, 0, 0 },
        { 0, 0, 0, 0 }
    }
};
 
int find_value(int y, int x, int k)
{
    int ret = 0;
 
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            ret += m[y + i][x + j] * v[k][i][j];
 
    return ret;
}
 
int main(void)
{
    int answer = 0;
 
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++)    scanf("%d", &m[i][j]);
    for (int i = R; i < R + 4; i++) for (int j = 0; j < C + 4; j++) m[i][j] = Min;
    for (int i = 0; i < R + 4; i++) for (int j = C; j < C + 4; j++)    m[i][j] = Min;
    
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            for (int k = 0; k < v.size(); k++)        
                answer = max(answer, find_value(i, j, k));
 
    printf("%d\n", answer);
 
    return 0;
}