백준 알고리즘 풀이 14500번 - 테트로미노

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

14500번: 테트로미노

 

dfs로 풀수 있던 간단한 문제.

 

알고리즘

---

1. dfs로 ㅗ모양을 제외한 도형을 움직이면서 도형안에 들어가는 최댓값을 구한다.

2. ㅗ모양 탐지를 위해서 도형을 돌려본다.

3. 1,2번에 대해 맵 전체를 돌면서 최댓값을 찾는다.

 

시간 복잡도

---

dfs의 시간복잡도가 O(V+E)인데, 맵을 N X M 이므로 총 O(NXM(V+E)).

 

소스코드

---

#include <iostream>
using namespace std;

int isVisited[501][501]={false,};
int map[501][501];
int sizeX,sizeY; 

int dx[5] = {0,1,-1,0,0};
int dy[5] ={0,0,0,1,-1};
// ㅗ 모양 움직일때 사용

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

// ㅗ모양을 제외한 도형을 움직이는 것으로.
int dfs(int x,int y,int count){
    if(count==4){
        return map[y][x];
    }
    int ans =0;

    for(int i=1;i<=4;i++){
        int nextX = dx[i]+x;
        int nextY = dy[i]+y;
        if(nextX>0 && nextX<=sizeX && nextY>0 && nextY<=sizeY){
            if(!isVisited[nextY][nextX]){
                isVisited[nextY][nextX] = true;
                ans = max(ans,map[y][x]+dfs(nextX,nextY,count+1));
                isVisited[nextY][nextX] = false;
            }
        }
    }
    return ans;
}

// ㅗ모양 도형을 움직이는 것으로
int middleF(int x,int y){
    int maximum =0;
    for(int i=0;i<4;i++){
        int ans = 0;
        bool check = false;
        for(int j=0;j<4;j++){
            int nowX = x+fuckX[i][j];
            int nowY = y+fuckY[i][j];
            if(nowX>sizeX || nowX<=0 || nowY>sizeY || nowY<=0){
                check = true;
                break;
            }
            ans += map[nowY][nowX];
        }
        if (check) {
            ans =0;
            continue;
        }
        
        if(maximum<ans) maximum = ans;
    }
    return maximum;
}

int main(){
    cin>>sizeY>>sizeX;
    for(int y=1;y<=sizeY;y++){
        for(int x=1;x<=sizeX;x++){
            cin>>map[y][x];
        }
    }
    int maximum = 0;
    for(int y=1;y<=sizeY;y++){
        for(int x=1;x<=sizeX;x++){
            isVisited[y][x] = true;
            
            int value = max(dfs(x,y,1),middleF(x,y));
            isVisited[y][x]=false;
            if(maximum<value){
                maximum = value;
            }
        }
    }
    cout<<maximum;   
    return 0;
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)