본문으로 바로가기

[DFS] 14500번 테트로미노

category Algorithm/BOJ 문제풀이 2019. 1. 16. 17:37
14500_테트로미노

14500번 테트로미노

 

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


 

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

  • 정사각형은 서로 겹치면 안된다.
  • 도형은 모두 연결되어 있어야 한다.
  • 정사각형의 꼭짓점끼리 연결되어 있어야 한다. 즉, 변과 꼭짓점이 맞닿아있으면 안된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

img

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

 

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

 

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

예제 입력

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1

 

예제 출력

19

20

7

 

해결방법

모든 경우를 매칭하여 최대값을 구하는 완전탐색 문제이다

 

 

⭐️ 솔루션 1 ⭐️

처음 문제를 보고 모든 도형을 저장한 뒤, 전체의 맵을 돌아보는 것을 생각했다

시간복잡도를 계산해봤는데 시간초과가 발생하지 않아서 이대로 구현을 했다

 

모든 도형은 1x1 정사각형 4개로 이뤄져있기 때문에 미리 모든 도형을 배열로 저장하였다

int tetromino[6][4][4][2] = {
   
}

 

그 다음 반복문을 통해 모든 도형을 매칭하여 값을 얻었다

// 행 탐색
for(int i=0; i<n; i++){
    // 열 탐색
    for(int j=0; j<m; j++){
        // 도형의 종류
        for(int k=0; k<6; k++){
            // 도형의 방향
            for(int d=0; d<4; d++){
                if(k == 0 && d>1) break;
                if(k == 1 && d>0) break;
                
                go_tetris(i,j,k,d);
            }
        }
    }
}

 

이렇게 단순구현 시, 시간복잡도는 아래와 같다

  • 전체 맵을 탐색 (n * m)
  • k 종류의 도형 매칭 (k)
  • 도형 4방향 회전 (d)
  • 1x1 정사각형 4개로 칸의 합 구하기 (i)

시간복잡도 : O(500^2 * 6 * 4 * 4) = O(24,000,000)

 

 

⭐️ 솔루션 2 ⭐️

하지만 구글링을 해보니 이 문제는 DFS 로 구현을 하는 문제였다....

그래서 다시 DFS 로 구현을 시도했다

시간복잡도를 계산해봤는데 시간초과가 발생하지 않아서 이대로 구현을 했다

 

새로운 솔루션은 DFS 탐색을 수행하는 것이다

한 노드에서 4번만큼 4방향으로 노드를 확장시킨다면?

'ㅗ' 도형을 제외한 모든 테트로미노의 경우가 나오게된다 !!!

그렇다면 dfs 로 나머지 도형을 탐색하고 'ㅗ' 도형만 예외로 처리를 해주면 된다 !!

 

DFS 구현 시, 시간복잡도는 아래와 같다

  • 전체 맵을 탐색 (n * m)
  • 각 노드별 DFS 탐색 (4^4)
  • 예외의 경우(ㅗ) 탐색 (4*4)
  • 1x1 정사각형 4개로 칸의 합 구하기 (i)

시간복잡도 : O(500^2 * (4^4 + 4*4)) = O(68,000,000)

 

 

 

소스코드

[ 단순 구현 ]

문제 해결 시간 : 50m

메모리 : 3212 KB

시간 : 60 ms

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define MAX 501
using namespace std;

/*
 
 테트리스의 모든 모양을 미리 선언을 하여 맞춰보는 구현방법
 
 - 전체 맵을 탐색 (n * m)
 - k 종류의 도형 매칭 (k)
 - 도형 4방향 회전 (d)
 - 1x1 정사각형 4개로 칸의 합 구하기 (i)
 
 시간복잡도 : O(500^2 * 6 * 4 * 4) = O(24,000,000)
 
*/

int n,m,ans;
int map[MAX][MAX];

// 종류, 방향, 블럭
int tetromino[6][4][4][2] = {
    // ㅡ 블럭
    {
        // 첫번째 방향
        { {0,0},{0,1},{0,2},{0,3} },
        // 두번째 방향
        { {0,0},{1,0},{2,0},{3,0} },
        // 세번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} },
        // 네번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} }
    },
    // ㅁ 블럭
    {
        // 첫번째 방향
        { {0,0},{0,1},{1,0},{1,1} },
        // 두번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} },
        // 세번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} },
        // 네번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} }
    },
    // ㄴ 블럭
    {
        // 첫번째 방향
        { {0,0},{1,0},{2,0},{2,1} },
        // 두번째 방향
        { {0,0},{0,1},{0,2},{1,0} },
        // 세번째 방향
        { {0,0},{0,1},{1,1},{2,1} },
        // 네번째 방향
        { {0,0},{0,1},{0,2},{-1,2} }
    },
    // ㄴ 블럭 (대칭)
    {
        // 첫번째 방향
        { {0,0},{0,1},{-1,1},{-2,1} },
        // 두번째 방향
        { {0,0},{1,0},{1,1},{1,2} },
        // 세번째 방향
        { {0,0},{0,1},{1,0},{2,0} },
        // 네번째 방향
        { {0,0},{0,1},{0,2},{1,2} }
    },
    // ⨫ 블럭
    {
        // 첫번째 방향
        { {0,0},{1,0},{1,1},{2,1} },
        // 두번째 방향
        { {0,0},{0,1},{-1,1},{-1,2} },
        // 세번째 방향
        { {0,0},{1,0},{1,-1},{2,-1} },
        // 네번째 방향
        { {0,0},{0,1},{1,1},{1,2} }
    },
    // ㅗ 블럭
    {
        // 첫번째 방향
        { {0,0},{0,-1},{0,1},{-1,0} },
        // 두번째 방향
        { {0,0},{-1,0},{1,0},{0,1} },
        // 세번째 방향
        { {0,0},{0,-1},{0,1},{1,0} },
        // 네번째 방향
        { {0,0},{-1,0},{1,0},{0,-1} }
    }
};

void go_tetris(int row,int col,int kind,int dir){
    int sum = 0;
    
    for(int i=0; i<4; i++){
        int nx = row + tetromino[kind][dir][i][0];
        int ny = col + tetromino[kind][dir][i][1];
        
        if(nx<0 || ny<0 || nx>= n || ny>=m) return;
        
        sum += map[nx][ny];
    }
    
    ans = max(ans,sum);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    
    ans = 0;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            for(int k=0; k<6; k++){
                for(int d=0; d<4; d++){
                    if(k == 0 && d>1) break;
                    if(k == 1 && d>0) break;
                    
                    go_tetris(i,j,k,d);
                }
            }
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

 

[ DFS 구현 ]

문제 해결 시간 : 50m

메모리 : 3212 KB

시간 : 84 ms

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define MAX 501
using namespace std;

/*
 
 한 노드에서 상하좌우 탐색을 4번 수행했을 때, 'ㅗ' 를 제외한 모든 테트로미노 모형이 된다
 따라서 'ㅗ' 를 예외처리로 두고 나머지를 DFS 탐색을 통해 수행하면 모든 경우를 탐색할 수 있다
 
 - 전체 맵을 탐색 (n * m)
 - 각 노드별 DFS 탐색 (4^4)
 - 에외 경우 탐색 (4*4)
 
 시간복잡도 : O(500^2 * (4^4 + 4*4)) = O(68,000,000)
 
*/

int n,m,ans;
int map[MAX][MAX];
bool visited[MAX][MAX];

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

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

void dfs(int x,int y,int cnt,int sum){
    // 테트로미노를 만든 경우
    if(cnt == 4){
        ans = max(ans,sum);
        return;
    }
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
        
        if(!visited[nx][ny]){
            visited[nx][ny] = true;
            dfs(nx,ny,cnt+1,sum+map[nx][ny]);
            visited[nx][ny] = false;
        }
    }
}

// 'ㅗ' 의 경우 예외처리
// 4방향 x 정사각형 4개
void getExceptionCase(int x,int y){
    for(int i=0; i<4; i++){
        bool flag = true;
        int sum = 0;
        
        for(int j=0; j<4; j++){
            int nx = x + exception_case[i][j][0];
            int ny = y + exception_case[i][j][1];
            
            if(nx<0 || ny<0 || nx>=n || ny>=m){
                flag = false;
                break;
            }
            
            sum += map[nx][ny];
        }
        
        if(flag)
            ans = max(ans,sum);
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    
    memset(visited, false, sizeof(visited));
    ans = 0;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            visited[i][j] = true;
            dfs(i,j,1,map[i][j]);
            visited[i][j] = false;
            
            // 'ㅗ' 의 경우 예외처리
            getExceptionCase(i,j);
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

 

저작자표시

'Algorithm > BOJ 문제풀이' 카테고리의 다른 글

[SIM] 3568번 iSharp  (0) 2019.01.17
[DFS] 3019번 테트리스  (0) 2019.01.17
[DFS] 12100번 2048 (Easy)  (0) 2019.01.16
[BFS] 15653번 구슬 탈출 4  (0) 2019.01.15
[DFS] 13460번 구슬 탈출 2  (0) 2019.01.15
댓글 , 엮인글
SuperM
블로그 이미지 슈퍼마리호 님의 블로그
MENU
CATEGORY
VISITOR 오늘 / 전체

티스토리툴바