[BaekJoon/백준] 2146번 다리 만들기

 

 

SCC 관련 문제가 많이 나오는 것 같다.

 

 

16234번 인구이동, 2234번 성곽 문제처럼

SCC 그룹을 정의하여 푸는 문제였습니다.

 

 

DFS로 SCC를 정의하고

BFS로 다리 최단길이를 정해주었습니다.

 

 

즉, 처음 DFS를 통해 각 섬의 종류를 분류하여 SCC 배열에 저장해주고

BFS를 통해, 다른 섬에 닿을때의 최솟값을 계산해줍니다.

 

 

주석을 풀어서 실행해보시면 이해에 도움이 되실 수 있을 것 같습니다.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;


int N;
int MAP[100][100];
int SCC[100][100];
int DEPTH[100][100];
bool VISIT[100][100];


int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

int G; // SCC 그룹정보. 섬의 종류를 나타내며 0부터 시작.
int MIN_DEPTH = 40000000;


// SCC 정보 등록
void dfs(int x, int y, int G) {
    
    
    VISIT[x][y] = true;
    SCC[x][y] = G;
    
    
    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 >= N)
            continue;
        
        if(!VISIT[tx][ty] && MAP[tx][ty] == 1)
            dfs(tx, ty, G);
    }
    
}

void bfs(int x, int y, int G) {
    
    
    queue<pair<int, int>> que;
    que.push({x, y});
    VISIT[x][y] = true;
    
    
    while(!que.empty()) {
        
        
        int xx = que.front().first;
        int yy = que.front().second;
        
        que.pop();
        
        
        for(int i = 0; i < 4; i++) {
            
            
            int tx = xx + mx[i];
            int ty = yy + my[i];
            
            
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= N)
                continue;
            
            
            if(!VISIT[tx][ty] && MAP[tx][ty] == 0) {
                
                // 바다만 본다~!
                
                que.push({tx, ty});
                VISIT[tx][ty] = true;
                DEPTH[tx][ty] = DEPTH[xx][yy] + 1;
                                
            } else if(MAP[tx][ty] == 1 && SCC[tx][ty] != G) {
                // 다른 섬에 정착
                // VISIT은 안해줘도.
                DEPTH[tx][ty] = DEPTH[xx][yy]; // 다리놓는거니까 섬까지는 + 1할필요 없음.
                
                if(MIN_DEPTH > DEPTH[tx][ty])
                    MIN_DEPTH = DEPTH[tx][ty];
                
            }
        }
        
    }
    
    
    
}

int main() {
    
    cin >> N;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> MAP[i][j];
        }
    }
        
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(!VISIT[i][j] && MAP[i][j] == 1) { //방문안함.
                dfs(i, j, ++G);
            }
        }
    }
    
    

    
//    for(int i = 0; i < N; i++) {
//        for(int j = 0; j < N; j++) {
//
//            cout << SCC[i][j] << " ";
//        }
//        cout << "\n";
//    }
//
//
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            
            if(MAP[i][j] == 1) {
                memset(VISIT, 0, sizeof(VISIT));
                memset(DEPTH, 0, sizeof(DEPTH));
                
                bfs(i, j, SCC[i][j]);
            }
        }
    }

    cout << MIN_DEPTH << "\n";
    
    
}

 

 

소요 시간 : 35분