2146-ブリッジ-BFSの作成


質問する



質問リンク:https://www.acmicpc.net/problem/2146

ポリシー

  • 島と島を結ぶためには、島と島を区別しなければならない.そのため、まず各分野を分ける.
  • Nは100以下で、領域ごとに計算される最大値はN^2なので、最大N^2個の領域は、N^4でも時間が十分なので、すべて探しました.
  • 領域でBFSルックアップが使用される.
  • の格子配列を作成し,重複する部分にアクセスしなかった.
  • コード#コード#

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int N;
    int mp[102][102];
    bool ch[102][102];
    int territoryCnt = 0;
    int territoryColor = 2;
    int territoryStart = 2;
    int dy[4] = {-1, 0, 1, 0};
    int dx[4] = {0, 1, 0, -1};
    struct road{
        int r, c, dis;
        road(int aa, int bb, int cc){
            r = aa;
            c = bb;
            dis = cc;
        }
    };
    
    // 영역을 구별해주는 함수이다. DFS로 구현하였다. 
    void findTerritory(int r, int c, int color){
        
        for(int i=0; i<4; i++){
            int rr = r+dy[i];
            int cc = c+dx[i];
            if(!ch[rr][cc] && mp[rr][cc] == 1){
                ch[rr][cc] = true;
                mp[rr][cc] = color;
                findTerritory(rr,cc,color);
            }
        }
    }
    
    // 각 영역마다 다른 대륙을 이으는 최소값을 구하는 것이다.
    int findRoadLength(int r, int c, int color){
        queue<road> q;
        q.push(road(r,c,0));
        ch[r][c] = true;
        // 먼저 해당위치에 값을 큐에 넣어준다. 
        while(!q.empty()){
            road ret = q.front();
            q.pop();
    
    		// 이동을 하며 찾되, 자기와 같은 색이 아니고 바다이거나 다른 대육일 떄 이동한다.
            for(int i=0; i<4; i++){
                int rr = ret.r+dy[i];
                int cc = ret.c+dx[i];
                // 바다가 아닌 다른 대륙일 경우 리턴해준다. 
                if(!ch[rr][cc] && mp[rr][cc] != 0 && mp[rr][cc] != color){
                    return ret.dis;
                }
                // 바다일경우 다시 queue에 넣어준다.
                else if(!ch[rr][cc] && mp[rr][cc] == 0 && rr > 0 && rr <= N && cc > 0 && cc<=N){
                    ch[rr][cc] =true;
                    q.push(road(rr,cc,ret.dis+1));
                }
            }
        }
        return 2147000000;
    }
    
    int main(){
        ios_base::sync_with_stdio(false);
        // freopen("../input.txt","rt",stdin);
        cin >> N ;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                cin >> mp[i][j];
            }
        }
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(mp[i][j] == 1){
                    memset(ch, false, sizeof(ch));
                    ch[i][j] = true;
                    mp[i][j] = territoryColor;
                    findTerritory(i, j, territoryColor);
                    territoryColor++;
                    territoryCnt++;
                }
            }
        }
        int res = 2147000000;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(mp[i][j] != 0){
                    memset(ch, false, sizeof(ch));
                    res = min(res,findRoadLength(i, j, mp[i][j]));
                }
            }
        }
        cout<<res<<endl;
        return 0;
    }
    
    
    

    感想


    これはDFSとBFSを組み合わせた興味深い問題である.時間の複雑さをうまく計算できれば,十分な探索が可能である.大陸の各部分には単独のBFSがあり、これは良いアイデアです.