9. 그래프, dfs, bfs

9.md

0.01MB

0. 복습
1. 그래프

그래프는 간선으로 연결된 정점들의 집합이다.

인접 행렬은 N제한이 적을 때 사용한다.

보통은 인접 리스트로 구현하지만, 말 그대로 연결리스트를 사용하지는 않고, vector를 사용할 것이다.

배열을 정점 개수만큼 잡아주고, 정점이 이어질때마다 하나씩 추가해준다.

• 단방향그래프 directed graph

방향이 있는 그래프. 한쪽 방향으로만 이동 가능

• 양방향그래프 undirected graph

방향이 없는 그래프. 양쪽 방향으로 모두 이동 가능

• 사이클 cycle

한 정점에서 출발해서 중복된 간선을 거치지 않고 다시 해당 정점으로 올 수 있으면 cycle이 있다고 한다.

• 트리 tree

사이클 없는 그래프.

• 루트 root

루트가 있는 트리, 루트트리는 부모자식관계를 정의할 수 있다.

2. 트리

트리에서는 간선의 개수 = 정점의 개수 - 1이다.

두 정점 사이에는 유일한 경로가 있다.

3. Directed Acyclic Graph

방향있는, 사이클 없는, 그래프 -> 따로 분류를 할 만큼 특별한 그래프이다.

이 그래프가 아니면 그래프 문제를 dp로 풀 수 없다.

4. degree 차수

deg(v) = 3 이라는건, v와 연결된 간선이 3개라는 것이다.

• indegree, outdegree

  indegree는 해당 정점에 들어오는 간선의 개수를, outdegree는 해당 정점에서 나가는 간선의 개수를 의미한다.

5. dfs

깊이 우선 탐색.

void dfs(int cur) {
    visited[cur] = true;
    for (int nxt : G[cur]) {      
        if (!visited[nxt])        
            dfs(nxt);
    }
}

참고 문제 : 11724

6. bfs

너비 우선 탐색

(1) queue에 맨 처음 정점을 push, 그 정점을 방문했다고 체크.

(2) queue가 빌때까지 queue의 front와 인접한 정점을 push. pop한번 해주는것도 잊지 말기.

참고 문제 : 1260

문제들 : 2606, 5567, 4963, 2667, 1012, 1058, 1389, 2644, 12849, 2468, 2178, 7562

99. 부록 : 참고 문제 풀이

11724

#include <iostream>
#include <vector>

using namespace std;

const int MAX_V = 10000;
vector<int> G[MAX_V];

bool visited[MAX_V];
void dfs(int cur){
    visited[cur]=true;
    for(int nxt : G[cur]) {
        if(!visited[nxt]) dfs(nxt);
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int N, M; cin >> N >> M;
    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);
    }

    int res=0;

    for(int i=0; i<N; ++i){
        if(!visited[i]) {
            dfs(i);
            res++;
        }
    }
    cout << res << '\n';
}

// O(N+M)

1260

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MN = 1e3;
vector<int> G[MN];
bool visited[MN];
bool visited_dfs[MN];

void dfs(int cur){
    visited_dfs[cur] = true;
    cout << cur+1 << ' '; 
    for(int nxt : G[cur]){
        if(!visited_dfs[nxt]) dfs(nxt);
    }
}

int main(){
    int N, M, k; cin >> N >> M >> k;
    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);
    }

    for(int i=0; i<N; ++i){
        sort(G[i].begin(), G[i].end());
    }

    dfs(k-1);
    cout << '\n';

    queue<int> q;
    q.push(k-1);
    visited[k-1] = true;

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur + 1 << ' ';
        for(int nxt : G[cur]) {
            if(!visited[nxt]) q.push(nxt);
            visited[nxt]=true;
        }
    }
    cout << '\n';
}

2606

#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 101;
vector<int> G[MAX_V];
bool visited[MAX_V];
int res=0;
void dfs(int cur){
    visited[cur] = true;
    res++;
    for(int nxt : G[cur]) {
        if(!visited[nxt]) dfs(nxt);
    }
}
int main(){
    int N; cin >> N;
    int M; cin >> M;
    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);
    }
    dfs(0);
    cout << res-1 << '\n';
}

5567

#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 501;
vector<int> G[MAX_V];
bool visited[MAX_V];
int res=0;

void search_depth_1(int cur){
    if(!visited[cur]) res++;
    visited[cur] = true;
    for(int nxt : G[cur]) {
        if(!visited[nxt]){
            visited[nxt]= true;
            res++;
        }
    }
}
int main(){
    int N; cin >> N;
    int M; cin >> M;
    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);
    }
    visited[0]=true;
    for(int it : G[0]) {
        search_depth_1(it);
    }

    cout << res << '\n';
}

4963

#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 51;
int arr[MAX_V][MAX_V];
bool visited[MAX_V][MAX_V];

int di[8]={-1, -1, 0, 1, 1, 1, 0, -1};
int dj[8]={0, 1, 1, 1, 0, -1, -1, -1};

int h, w;

void dfs(int ci, int cj){
    visited[ci][cj] = true;
    for(int d=0; d<8; ++d){
        int ni = ci+di[d];
        int nj = cj+dj[d];
        if(ni>=0 && nj>=0 && ni<=h && nj<=w) {
            if(arr[ni][nj]==1 && !visited[ni][nj]) dfs(ni, nj);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    while(1){    
        int res=0;
        cin >> w >> h;
        if(h==0 && w == 0) break;
        for(int i=0; i<MAX_V; ++i){
            for(int j=0; j<MAX_V; ++j){
                arr[i][j] = 0;
                visited[i][j] = 0;
            }
        }
        for(int i=0; i<h; ++i){
            for(int j=0; j<w; ++j){
                cin >> arr[i][j];
            }
        }
        for(int i=0; i<h; ++i){
            for(int j=0; j<w; ++j){
                if(arr[i][j]==1 && !visited[i][j]){
                    res++;
                    dfs(i, j);
                }
            }
        }
        cout << res << '\n';
    }
}

2667

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

string arr[30];
bool visited[30][30];

int di[4]={-1, 0, 1, 0};
int dj[4]={0, -1, 0, 1};

int N;


int bfs(int ci, int cj){
    queue<pair<int, int> > q;
    int res=0;
    visited[ci][cj]=true;
    q.push({ci, cj}); res++;
    while(!q.empty()){
        ci = q.front().first;
        cj = q.front().second;
        q.pop();
        for(int d=0; d<4; ++d){
            int ni=ci+di[d];
            int nj=cj+dj[d];
            if(ni>=0 && ni<N && nj>=0 && nj<N){
                if(arr[ni][nj]=='1' && !visited[ni][nj]) {
                    q.push({ni, nj}); res++; visited[ni][nj]=true;
                }
            }
        }
    }
    return res;
}
int main(){
    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }
    vector<int> v;
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(arr[i][j] == '1' && !visited[i][j]) {
                v.push_back(bfs(i, j));
            }
        }
    }
    sort(v.begin(), v.end());
    cout << v.size() << '\n';
    for(int i=0; i<v.size(); ++i){
        cout << v[i] << '\n';
    }
}

1012

#include <iostream>
#include <vector>
using namespace std;

const int MAX_V = 101;
int arr[MAX_V][MAX_V];
bool visited[MAX_V][MAX_V];

int di[4]={-1, 0, 1, 0};
int dj[4]={0, -1, 0, 1};

int N, M;

void dfs(int ci, int cj){
    visited[ci][cj] = true;
    for(int d=0; d<4; ++d){
        int ni = ci+di[d];
        int nj = cj+dj[d];
        if(ni>=0 && nj>=0 && ni<N && nj<M) {
            if(arr[ni][nj]==1 && !visited[ni][nj]) dfs(ni, nj);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int T; cin >> T;
    while(T--){    
        for(int i=0; i<MAX_V; ++i){
            for(int j=0; j<MAX_V; ++j){
                arr[i][j] = 0;
                visited[i][j] = 0;
            }
        }
        int res=0;
        int K;
        cin >> M >> N >> K;
        for(int i=0; i<K; ++i){
            int a, b;
            cin >> a >> b;
            arr[b][a] = 1;
        }
        for(int i=0; i<N; ++i){
            for(int j=0; j<M; ++j){
                if(arr[i][j]==1 && !visited[i][j]){
                    res++;
                    dfs(i, j);
                }
            }
        }
        cout << res << '\n';
    }
}

1058

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool arr[51][51];
bool arr2[51][51];
int cnt[51];
int maxcnt = 0;
int main() {
    int N;    cin >> N;
    for (int i = 0; i < N; ++i) {
        string a; cin >> a;
        for (int j = 0; j < a.size(); ++j) {
            if (a[j] == 'Y') {
                arr[i][j] = true;
                cnt[i]++;
                if (cnt[i] > maxcnt) maxcnt = cnt[i];
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N-1; ++j) {
            if (i == j) continue;
            if (!arr[i][j]) continue;
            for (int k = j + 1; k < N; ++k) {
                if (!arr[i][k]) continue;
                //arr[i][j] : true, arr[i][k] : true, j와k는 2-친구
                if (arr[j][k] || arr2[j][k]) continue; //이미 2-친구
                arr2[j][k] = true;
                arr2[k][j] = true;
                cnt[j]++;
                cnt[k]++;
                maxcnt = max(maxcnt, max(cnt[j], cnt[k]));
            }
        }
    }
    cout << maxcnt << '\n';
}

1389

//플로이드 워셜
#include <iostream>
using namespace std;

const int INF = 987654321;
const int nil = -1;
int arr[101][101];
int main() {
    int N, M; cin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int a, b; cin >> a >> b;
        arr[a][b] = 1;
        arr[b][a] = 1;
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (arr[i][j] != 1) arr[i][j] = INF;
        }
    }

    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (arr[i][k] + arr[k][j] < arr[i][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }

    int res = INF + 1;
    int resIdx = -1;

    for (int i = 1; i <= N; ++i) {
        int cnt = 0;
        for (int j = 1; j <= N; ++j) {
            if (i == j) continue;
            if (arr[i][j] != INF) cnt += arr[i][j];
        }
        if (cnt < res) {
            res = cnt;
            resIdx = i;
        }
    }
    cout << resIdx << '\n';


}

2644

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> arr[101];;
bool visited[101];
int main() {
    int N; cin >> N;
    int r1, r2; cin >> r1 >> r2;
    int M; cin >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y; cin >> x >> y;
        arr[x].push_back(y);
        arr[y].push_back(x);
    }
    if (r1 == r2) {
        cout << '0' << '\n';
        return 0;
    }
    queue<pair<int, int> > q;
    visited[r1] = true;
    q.push({ r1, 0 });
    while (!q.empty()) {
        pair<int, int> p1;
        p1 = q.front();
        q.pop();
        if (p1.first == r2) {
            cout << p1.second << '\n';
            return 0;
        }
        for (int i = 0; i < arr[p1.first].size(); ++i) {
            if (visited[arr[p1.first][i]]) continue;
            q.push({ arr[p1.first][i], p1.second+1 });
            visited[arr[p1.first][i]] = true;
        }
    }
    cout << "-1" << '\n';
}

12849

#include <iostream>
#include <vector>
using namespace std;
const int mod = 1e9 + 7;
int dp[8][100001];
vector<int> arr[8] = {
    {1, 2},
    {0, 2, 3},
    {0, 1, 3, 4},
    {1, 2, 4, 5},
    {2, 3, 5, 7},
    {3, 4, 6},
    {5, 7},
    {4, 6},
};
int main() {
    int D; cin >> D;
    dp[1][1] = 1;
    dp[2][1] = 1;
    for (int t = 2; t <= D; ++t) {
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < arr[i].size(); ++j) {
                dp[i][t] = (dp[i][t]%mod + dp[arr[i][j]][t - 1]%mod)%mod;

            }
        }
    }
    cout << dp[0][D] << '\n';
}

2468

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100][100];
int N;
int di[4] = { -1, 0, 1, 0 };
int dj[4] = { 0, -1, 0, 1 };
bool visited[100][100];
void dfs(int x, int y, int h) {
    if (!visited[x][y]) {
        visited[x][y] = true;
        for (int d = 0; d < 4; ++d) {
            int ni = x + di[d];
            int nj = y + dj[d];
            if (ni >= 0 && ni < N && nj >= 0 && nj < N) {
                if(arr[ni][nj]>h) dfs(ni, nj, h);
            }
        }
    }
}
int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> arr[i][j];
        }
    }
    int res = -1;
    for (int h = 0; h <= 100; ++h) {
        int cnt = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                visited[i][j] = false;
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (!visited[i][j] && arr[i][j] > h) {
                    dfs(i, j, h);
                    cnt++;
                }
            }
        }
        res = max(res, cnt);
    }
    cout << res << '\n';
}

2178

#include <iostream>
#include <string>
#include <queue>
using namespace std;
string arr[100];
bool visited[100][100];
int di[4] = { -1, 0, 1, 0 };
int dj[4] = { 0, -1, 0, 1 };
struct T {
    int i, j;
    int cnt;
};
int main() {
    int N, M;    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }
    queue<T> q;
    q.push({0, 0, 1});
    while (!q.empty()) {
        T f = q.front();
        if (f.i == N-1 && f.j == M-1) {
            cout << f.cnt << '\n';
            break;
        }
        q.pop();
        for (int d = 0; d < 4; ++d) {
            int ni = f.i + di[d];
            int nj = f.j + dj[d];
            if (ni >= 0 && ni < N && nj >= 0 && nj < M) {
                if (arr[ni][nj] == '1' && !visited[ni][nj]) {
                    visited[ni][nj] = true;
                    q.push({ ni, nj, f.cnt + 1 });
                }
            }
        }
    }
}

7562

#include <iostream>
#include <queue>
using namespace std;
int di[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dj[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
bool visited[300][300];

int main() {
    int T; cin >> T;
    while (T--) {
        int l; cin >> l;
        int a, b, c, d; 
        cin >> a >> b;
        cin >> c >> d;
        queue<pair<int, pair<int, int> > > q;
        q.push({ a, {b, 0} });
        for (int i = 0; i < 300; ++i) {
            for (int j = 0; j < 300; ++j) {
                visited[i][j] = false;
            }
        }
        visited[a][b] = true;
        while (!q.empty()) {
            pair<int, pair<int, int> > F = q.front();
            q.pop();
            if (F.first == c && F.second.first == d) {
                cout << F.second.second << '\n';
                break;
            }
            for (int d = 0; d < 8; ++d) {
                    int ni = F.first + di[d];
                    int nj = F.second.first + dj[d];
                    if (ni >= 0 && ni < l && nj >= 0 && nj < l) {
                        if (!visited[ni][nj]) {
                            q.push({ ni, {nj, F.second.second+1} });
                            visited[ni][nj] = true;
                        }
                    }
            }
        }
    }
}