[백준] 모양 만들기

백준 문제를 보던 중 그래도 재미있는 문제를 푼거같은 기분이 든다. 0으로 나온 숫자를 1로 바꿀경우 인접해있는 1의 최대 숫자를 출력하면 되는 문제인데 예전에 리트코드에서도 비슷한 문제를 봐서 똑같이 접근해봤다.

말 그대로 완전탐색 문제이기때문에 숫자를 한번 1로 바꾸고 dfs 로 계산하는 방법을 선택했지만 시간초과를 받았다. 조금 더 최적화 하는 방법을 생각했고 0을 1로 바꾸면서 dfs 를 계속 반복적으로 하는것보다 1을 묶음으로 만들어서 그룹 번호를 매기고 최대값을 저장하는 방법을 선택했다.

그룹에 번호를 붙히고 그 다음에는 최대 연결 길이를 저장함으로서 dfs를 Matrix 한번 도는 시점에서 끝내고. 0을 1로 바꾼다는 가정하에 상하좌우 방향에서 포함되는 모든 1을 저장했다. 그리고 번호 순서대로 탐색을 해야해서 정렬을 하였고 만약 그룹 숫자가 바뀌면은 최대 연결 숫자를 계속 더해줌으로서 시간초과 없이 통과할 수 있었다.

굉장히 재밌는 문제라고 생각했고 나름의 생각이 많이 포함되야 하기 때문에 골드3의 문제라고 판정됐다고 생각한다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N,M; 
int matrix[1001][1001]; 
bool visited[1001][1001]; 
vector<pair<int,int>> savePoints; 
pair<int,int> saveVisited[1001][1001]; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 


void Input(){
    cin >> N >> M; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> matrix[i][j]; 
        }
    }
}

int dfs(int i, int j){
    if(i < 0 || i >= N || j < 0 || j >= M || matrix[i][j] == 0 || visited[i][j]) return 0; 
    visited[i][j] = true; 
    savePoints.push_back({i,j}); 
    int cnt = 1; 
    cnt += dfs(i+1,j);
    cnt += dfs(i-1,j); 
    cnt += dfs(i,j+1);
    cnt += dfs(i,j-1); 
    return cnt; 

}

void Solution(){
    int answer = INT_MIN; 
    int cnt = 1; 
    int curr_max = 0; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(matrix[i][j] == 1 && !visited[i][j]){
                curr_max = dfs(i,j); 
                for(pair<int,int>& p : savePoints){
                    saveVisited[p.first][p.second] = {cnt,curr_max}; 
                }
                savePoints.clear(); 
                curr_max = 0;
                cnt++; 
            }
        }
    }
    vector<pair<int,int>> tmp; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(matrix[i][j] == 0){
                for(pair<int,int>& p : dir){
                    int nX = i + p.first;
                    int nY = j + p.second;
                    if(nX < 0 || nX >= N || nY < 0 || nY >= M || matrix[nX][nY] == 0) continue; 
                    
                    tmp.push_back(saveVisited[nX][nY]); 
                }
                pair<int,int> tmpNum = {-1,1}; 
                sort(tmp.begin(),tmp.end()); 
                for(pair<int,int>& p : tmp){
                    if(p.first != tmpNum.first){
                        tmpNum.first = p.first;
                        tmpNum.second += p.second; 
                    }
                }
                answer = max(answer,tmpNum.second);  
                tmp.clear(); 
            }
        }
    }
    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}