[DFS] 백준 14500번 테트로미노(C++)

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

 

뭔가 유명한가 했더니, 삼성 코딩테스트 문제로 나왔던 것!

 

우선 문제에 대한 설명부터 하자면 주어진 n * m 도화지에 저 모양중 하나(대칭 , 방향전환가능)을 넣엇을때 최댓값이 되는 값을 찾으라는 것

이 입력에 대해서 왜 40이냐고?

 

테트로미노 모양으로 딱 4개의 수직인 도형을 포함해서 그렇거등

 

뭐 문제에 대한 이해는 어렵지 않으니 바로 넘어가고

 

 

 

이건 진짜 나도 못풀겠어서 1시간동안 끙끙대다가 결국 답지를 봐버림

 

브루트포스인줄 알았더니 알고보니 브루트 포스로 풀려면 가능한 모든 경우의 수 (19가지)를 다 감안해서 해야하드라고..

 

그래서 아직 dfs에 익숙하진 않지만, dfs방법대로 푸는것이 정석이고 질문게시판에도 dfs로 푼분들이 많아서 한번 생각해봄

 

1. 어떤 한 점에서, 4가지 방향으로 가는 경우 중 하나를 선택

2. 그 방향을 계속 선택하다가 그 방향이 4번째 온 방향이면  종료 후 값을 보존

3. 보존한 값과 max값 비교

#include <iostream>

#include <cmath>

using namespace std;

int map[501][501];

bool visited[501][501];

int ans = 0;

int dx[4] = {-1, 1, 0, 0};

int dy[4] = {0, 0, -1, 1};

int n, m;

void find(int depth, int x, int y, int sum)

{

    int tx, ty;

    if (depth == 4)

    {

        ans = max(ans, sum);

        return;

    }

    for (int i = 0; i < 4; i++)

    {

        tx = x + dx[i];

        ty = y + dy[i];

        if (tx >= 0 && ty >= 0 && tx < n && ty < m && !visited[tx][ty])

        {

            visited[tx][ty] = true;

            find(depth + 1, tx, ty, sum + map[tx][ty]);

            visited[tx][ty] = false;

        }

    }

}

void checkExtraShape(int x, int y)

{

    int shapes[4][4][2] = {

        {{0, 0}, {-1, 0}, {0, -1}, {0, 1}},

        {{0, 0}, {1, 0}, {0, -1}, {0, 1}},

        {{0, 0}, {-1, 0}, {1, 0}, {0, -1}},

        {{0, 0}, {-1, 0}, {1, 0}, {0, 1}}};

    for (int i = 0; i < 4; i++)

    {

        int temp = 0;

        bool isValid = true;

        for (int j = 0; j < 4; j++)

        {

            int tx = x + shapes[i][j][0];

            int ty = y + shapes[i][j][1];

            if (tx < 0 || ty < 0 || tx >= n || ty >= m)

            {

                isValid = false;

                break;

            }

            temp += map[tx][ty];

        }

        if (isValid)

            ans = max(ans, temp);

    }

}

int main()

{

    int x, y;

    cin >> n >> m;

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < m; j++)

        {

            cin >> map[i][j];

        }

    }

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < m; j++)

        {

            visited[i][j] = true;

            find(1, i, j, map[i][j]);

            visited[i][j] = false;

            checkExtraShape(i, j);

        }

    }

    cout << ans << '\n';

    return 0;

}

 

 

해당 코드는 정답코드인데, 코드없이 설명하기에는 나의 역량이 부족하기에 코드로 설명을 진행하겠다.

int dx[4] = {-1, 1, 0, 0};

int dy[4] = {0, 0, -1, 1};

먼저 이것은 각 방향에 대한 배열이다

 

우리는 위에서 말했듯이 각 4방향으로 전진하는걸 보여준다 했잖아

 

 for (int i = 0; i < 4; i++)

    {

        tx = x + dx[i];

        ty = y + dy[i];

}

그래서 이 for문을 통해 dx가 왼쪽 오른쪽을 결정하고 dy는 위 아래를 결정하지

저기서 각각 하나를 선택하면 무조건 위 아니면 아래, 옆으로 선택된다.

 

안에있는 조건문은 간단하다 격자안을 벗어나면 find가 안되는 것! 

 

재귀문이 시작되기 전에 visited 라는 bool array를 활성화 시켜줌으로써 해당 재귀가 진행중일때 이미 지나간 곳은 지나가지 않게 한다.!

 

예를들어 우리가  [0][0]  > [0][1] > [0][2] 상태일때 [0][1]로 돌아가면 안되니까 !

 

하지만 우리가 이런 방법으로 문제를 풀면 다시 되돌아가서 중간으로 나오는

ㅗ ㅜ ㅏ ㅓ 모양들이 안되는데, 이건 하드코딩으로 따로 해줘야 한다.

 

void checkExtraShape(int x, int y)

{

    int shapes[4][4][2] = {

        {{0, 0}, {-1, 0}, {0, -1}, {0, 1}},

        {{0, 0}, {1, 0}, {0, -1}, {0, 1}},

        {{0, 0}, {-1, 0}, {1, 0}, {0, -1}},

        {{0, 0}, {-1, 0}, {1, 0}, {0, 1}}};

 

    for (int i = 0; i < 4; i++)

    {

        int temp = 0;

        bool isValid = true;

        for (int j = 0; j < 4; j++)

        {

            int tx = x + shapes[i][j][0];

            int ty = y + shapes[i][j][1];

            if (tx < 0 || ty < 0 || tx >= n || ty >= m)

            {

                isValid = false;

                break;

            }

            temp += map[tx][ty];

        }

        if (isValid)

            ans = max(ans, temp);

    }

 

}

이것또한 앞에서와 같이 shapes 에 대한 좌표들 하드코딩 + 값을 단순히 더해줌.

valid하지 않은건 격좌 안에 포함되지 않은것

 

하..어렵다.