백준, BOJ, 14500번, 테트로미노: C++ [CPP]

 

이것도 정말 구현문제로써

시키는대로 하면 된다.

다만 어떻게 구현할까? 의 선택지에서

DFS를 골랐다면 고생을 덜 할 것이었다

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

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

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

int N,M;
int map[500][500];
bool visited[500][500];


// 멍청했따.. 어차피 4칸을 사용하는 건데... DFS로 풀었으면 되었다는 힌트를 듣고.. 현타온다.
//즉 DFS로 4칸 탐색하는 과정에 일자 모양도 있고 네모도있고 기역자도 있다.
//다만 ㅗ 모양만 DFS로 탐색은 불가능하다.

int DFS(int x, int y, int cnt){
    //4개 탐색하면 종료. 4번쨰 노드 값 반환
    if(cnt == 4){
        return map[x][y];
    }
    
    int sum = 0;


    for(int dir = 0; dir<4; dir++){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if(nx<0 || nx>=N || ny<0 || ny>= M) continue;
        if(visited[nx][ny] != 0 )continue;
        //4가지 방향으로 다 DFS 진행시켜봄
        visited[nx][ny] = true;
        sum = max(sum, map[x][y] + DFS(nx, ny, cnt + 1)); //4개 탐색한 것들의 결과 중에 가장 큰 값 -> sum
        visited[nx][ny] = false;
        //해당 방향으로 DFS가 끝났으면 다른 경로를 탐색하기 위해 false를 해줘야 한다. 백트래킹하고 비슷
    }
    
    return sum;
}

//ㅗ 모양
//DFS로 판별할 수 없는 테트로미노

int hshape(int x, int y)
{
        int result = 0;
        //ㅗ (현재 좌표 ㅡ의 가운데)
        if (x >= 1 && y >= 1 && y < M - 1)
                 result = max(result, map[x][y - 1] + map[x][y] + map[x - 1][y] + map[x][y + 1]);
       
        //ㅏ (현재 좌표 ㅣ의 가운데)
        if (x >= 1 && x < N - 1 && y < M - 1)
                 result = max(result, map[x - 1][y] + map[x][y] + map[x][y + 1] + map[x + 1][y]);

        //ㅜ (현재 좌표 ㅡ의 가운데)
        if (x >= 0 && x < N - 1 && y < M - 1)
                 result = max(result, map[x][y - 1] + map[x][y] + map[x + 1][y] + map[x][y + 1]);

        //ㅓ (현재 좌표 ㅣ의 가운데)
        if (x >= 1 && x < N - 1 && y >= 1)
                 result = max(result, map[x - 1][y] + map[x][y] + map[x][y - 1] + map[x + 1][y]);

        return result;

}








int main(){
    cin >> N >> M;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
    int result = 0;
    
    //모든 좌표에 대해 수행
    for(int i=0; i<N; i++){
        for (int j = 0; j<M; j++)
        {
            visited[i][j] = true; //기준좌표 방문
            result = max(result, DFS(i, j, 1));
            result = max(result, hshape(i, j));
            visited[i][j] = false; //해당 좌표 미방문 처리해줘야함.
        }
    }

    cout << result;
    return 0;

}

 

어차피 4칸을 탐색하는 경우에서

저런 경우가 다 나오더라

ㅗ 모양만 제외하면 DFS 4칸 탐색 경로가 곧 저 모양이더라.

근데 나는 각 방향에 대해 다 하나하나.. 하고있어서 시간이 걸렸다.