深さ優先探索を学ぶ

AtCoder 版！蟻本 (初級編)

今日からAtCoder 版！蟻本 (初級編)の記事を読み進めましょう！
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

深さ優先探索

一番最初の状態から遷移を繰り返すことで辿り着ける全ての状態を生成します。

例題

例題 2-1-2 Lake Counting (POJ No.2386)

問題文は蟻本を参照してください。(ここに記載すると著作権の問題が発生します。)

• 処理はO(N^2)
• 深さ優先探索(dfs)を使用します。

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<cmath>
# include<cstdio>
# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

# define MAX_H 100
# define MAX_W 100

int n, m;
string field[MAX_H][MAX_W];

void dfs(int h, int w){
    field[h][w] = ".";
    for(int dy=-1; dy<=1; dy++){
        for(int dx=-1; dx<=1; dx++){
            int nx = w+dx;
            int ny = w+dy;
            
            if(0<nx && nx<n && 0<ny && ny<m && field[ny][nx] == "W" ){
                dfs(ny, nx);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> n >> m;
    
    for(int h=0; h<n; h++){
        for(int w=0; w<n; w++){
            cin >> field[h][w];
        }
    }
    
    int res = 0;
    for(int h=0; h<n; h++){
        for(int w=0; w<n; w++){
            if(field[h][w] == "W"){
                dfs(h,w);
                res++;
            }
        }
    }
    
    cout << res << endl;
    
    return 0;
}

A - 深さ優先探索

問題文はAtCoderを参照してください。

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<cmath>
# include<cstdio>
# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

# define MAX_H 500
# define MAX_W 500

int h, w;
string field[MAX_H][MAX_W];
bool ans = false;

void bfs(int x, int y){
    if(field[y][x] == "g") ans = true;
    
    field[y][x] = "#";
    
    for(int d=-1; d<=1; d++){
        int nx = x + d;
        int ny = y + d;
        if(0<=nx&&nx<w){
            if(field[y][nx] == "." || field[y][nx] == "g") bfs(nx, y);
        }
        if(0<=ny&&ny<h){
            if(field[ny][x] == "." || field[ny][x] == "g") bfs(x, ny);
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> h >> w;
    
    for(int y=0; y<h; y++){
        string s;
        cin >> s;
        for(int x=0; x<w; x++){
            field[y][x] = s[x];
        }
    }
    
    for(int y=0; y<h; y++){
        for(int x=0; x<w; x++){
            if(field[y][x] == "s"){
                bfs(x, y);
                goto END;
            }
        }
    }
    
    END:
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

B - 埋め立て

問題文はAtCoderを参照してください。

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<cmath>
# include<cstdio>
# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

# define MAX_H 10
# define MAX_W 10
string field[MAX_H][MAX_W];
bool check_field[MAX_H][MAX_W];
int res = 0;

void dfs(int x, int y){
    if(check_field[x][y]) return;
    check_field[x][y] = true;
    
    if(x-1>=0 && field[y][x-1]=="o") dfs(x-1, y);
    if(x+1<MAX_W && field[y][x+1]=="o") dfs(x+1, y);
    if(y-1>=0 && field[y-1][x]=="o") dfs(x, y-1);
    if(y+1<MAX_H && field[y+1][x]=="o") dfs(x, y+1);
    
    res++;
}

bool checkField(int x, int y){
    if(field[y][x]=="o") return false;
    
    int sum=0;
    if(x-1>=0 && field[y][x-1]=="o") sum++;
    if(x+1<MAX_W && field[y][x+1]=="o") sum++;
    if(y-1>=0 && field[y-1][x]=="o") sum++;
    if(y+1<MAX_H && field[y+1][x]=="o") sum++;
    
    if(sum>=2) return true;
    return false;
}

int main(int argc, const char * argv[]) {
    
    int sum=0;
    for(int i=0; i<MAX_H; i++){
        string s;
        cin >> s;
        for(int j=0; j<MAX_W; j++){
            field[i][j] = s[j];
            check_field[i][j] = false;
            if(s[j] == 'o') sum++;
        }
    }
    
    for(int i=0; i<MAX_H; i++){
        for(int j=0; j<MAX_W; j++){
            if(checkField(i, j)){
                dfs(i, j);
                if(res==sum+1){
                    cout << "YES" << endl;
                    goto END;
                }else{
                    for(int i=0; i<MAX_H; i++){
                        for(int j=0; j<MAX_W; j++){
                            res=0;
                            check_field[i][j] = false;
                        }
                    }
                }
            }
        }
    }
    
    cout << "NO" << endl;
    END:
    
    return 0;
}

B - バウムテスト

問題文はAtCoderを参照してください。

• 一度通過した頂点を判定できるようにbool型で保持をする
• for文にて各頂点をから一度も探索した事がない場合に限りdfsを行う。
• dfsにて繋がっている頂点を探索。
• 双方向にて各辺のデータを保持。これをしないと下記のような入力の場合、WAになる。

input

5 4
1 5
3 5
3 4
2 4

• 双方向で登録された前回と同じ値は処理を行わない
• 一度通過した頂点がある際は閉路があると判定を行う。
• 最後にdfsを呼び出す
• 計算量はO(n+m)なのでO(n)

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<cmath>
# include<cstdio>
# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

bool is_cycle=true;
vector<bool> going;

void dfs(vector<vector<int>>& G, int v, int prev_v){
    going[v] = true;
    
    for(auto next_v: G[v]){
        if(next_v == prev_v) continue;
        if(going[next_v]){
            is_cycle = false;
            continue;
        }
        dfs(G, next_v, v);
    }
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> G(n);
    for(int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    going.assign(n, false);
    
    int res=0;
    for(int i=0; i<n; i++){
        if(!going[i]){
            is_cycle = true;
            dfs(G, i, -1);
            if(is_cycle) res++;
        }
    }
    
    cout << res << endl;
    return 0;
}