[BaekJoon/백준] 2234번 성곽

 

 

차근 차근 단계별로 설명에 이해를 돕겠습니다.

 

문제의 의도 자체는 연구소같은 벽에 관한 브루트포스같은데, 그렇지 않고도 가능할 것 같다는 생각이 들었습니다.
 

저는 SCC 개념을 이용했습니다.

 

 

연합 문제처럼 SCC를 구해줍니다. 0 1 2 3..로 SCC 그룹 지정

 

dfs를 하면서, 닿을 수 있는 곳까지 닿는 것들은 같은 SCC에 있습니다.

 

그리고 벽을 부쉈을 떄 가장 큰 방을 구하는 방법은

인접한 SCC끼리 합쳤을 때 제일 커질 수 있는 경우를 구하면 됩니다.
 
SCC 각각의 갯수를 벡터에 저장해놓았다가
 
각 위치에서 상하좌우 봤을때 SCC 그룹값이 지금이랑 다르면(다른 SCC면), 더했을 때 SCC 최대인가 비교하면 됩니다.
 

 

---

 

서 : 1

북 : 2

동 : 4

남 : 8

 

이므로, 다 더하면 15입니다. 문제에서 주어지는 입력값은 벽이 있는 위치를 더한 값들입니다.

 

입력을 받자마자 15에서 빼줌으로써, 벽이 없는(이동할 수 있는) 위치값들을 갖게끔 변형해줍니다.

 

 

그리고 각 위치에서 DFS를 돌면서, 갈때까지 가면서, 갈 수 있는 곳은 같은 SCC에 있음을 보여줍니다.

 

SCC_COUNT를 이용해 전체 SCC 갯수를 세면서도, SCC 그룹의 이름(0부터 시작)들을 지정해주는데도 이용합니다.

DFS 한 차례가 끝나면, S 벡터에 COUNTER 값을 넣어줌으로써, 해당 SCC 그룹의 방의 갯수를 넣어줍니다.

 

이렇게 되면 S[0]에는 SCC 0의 방의 갯수가 담깁니다.

 

 

그리고 EVALUATE 함수를 이용해, 현재 위치와 인접한 위치의 SCC 그룹값이 다르다면

방의 갯수들을 더해보고 최댓값을 찾는 과정을 거칩니다.

 

주석을 풀어 가시며 실행해보시면 좋을 것 같습니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int MAP[50][50]; // 맵
int SCC[50][50]; // SCC 그룹값
bool VISIT[50][50];

int N, M;

vector<int> S; // 각 SCC그룹의 인원을 담을 벡터.
int SCC_COUNT; // S.size() == SCC_COUNT. SCC 갯수
int COUNTER; // 각 SCC 그룹의 인원을 계산할 때 쓰임.

int MIXED_MAX; // 합쳐진 방 넓이의 최대.

// 서 북 동 남
int D[4] = {1, 2, 4 ,8};

// 서 북 동 남
int mx[4] = {0, -1, 0, 1};
int my[4] = {-1, 0, 1, 0};

void dfs(int x, int y, int G) {
    
    VISIT[x][y] = true;
    SCC[x][y] = G;
    COUNTER++; // 각 SCC 그룹 안의 인원이 몇인지 체크하기 위해
    
    for(int i = 3; i >= 0; i--) {
        
        if(MAP[x][y] >= D[i]) { // 갈 수 있는 지점이라면
            
            MAP[x][y] -= D[i];
            
            // 갈 수 있는 곳이다. 맵을 벗어나지도 않는다.
            int tx = x + mx[i];
            int ty = y + my[i];
            
            if(!VISIT[tx][ty])
                dfs(tx, ty, G);
            
            
        }
    }
}


void EVALUATE(int x, int y) {
    
    
    // 상하좌우 인접된 SCC값이 다르다 == 분리되어 있다 == 합칠 수 있다.
    for(int i = 0; i < 4; i++) {
        
        int tx = x + mx[i];
        int ty = y + my[i];
        
        if(tx < 0 || tx >= N || ty < 0 || ty >= M) // 맵 벗어나는 지점 무시.
            continue;
        
        
        if(SCC[x][y] != SCC[tx][ty]) {
            
            int V = S[SCC[x][y]] + S[SCC[tx][ty]]; // S[0]는 SCC 0의 갯수가 들어 있고, S[1]은 SCC 1의 갯수가 들어 있고..
            
            if(V > MIXED_MAX)
                MIXED_MAX = V;
            
        }
        
        
    }
    
    
}

int main() {
    
    
    cin >> M >> N;
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < M; j++) {
            
            cin >> MAP[i][j];
            MAP[i][j] = 15 - MAP[i][j]; // 벽이 뚫린 지점들의 값을 갖고 있도록 재설정. 1 + 2 + 4 + 8 = 15
            
        }
    }
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < M; j++) {
            
            if(!VISIT[i][j]) {
                COUNTER = 0;
                dfs(i, j, SCC_COUNT++);
                S.push_back(COUNTER); // SCC_COUNT == S.size() == 이 성에 있는 방의 갯수. 가장넓은 방의 넓이는 S안의 원소 중 MAX값.
            }
        }
    }
    
    
//    for(int i = 0; i < N; i++) {
//
//        for(int j = 0; j < M; j++)
//            cout << SCC[i][j] << " ";
//        cout << "\n";
//    }

//    for(int i = 0; i < S.size(); i++) {
//        cout << S[i] << " ";
//    } cout << "\n";
//
    
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            EVALUATE(i, j); // 방을 합쳐본다.
            
        }
    }
    
    sort(S.begin(), S.end(), greater<>()); // 내림차순 정렬
    cout << SCC_COUNT << "\n" << S[0] << "\n" << MIXED_MAX << "\n";
}

 

 

깊게 들어가서 집착하는 생각 1도없이 자신감있게 구현했는데, 한번에 통과했다. 자신감이 최고다

 

 

 

소요 시간 : 30분