백준 BOJ 풀이 : 그래프 이론 문제들 (Silver I ~ Gold) 220729

백준 BOJ 24935번 : Travelling Caterpillar

문제 난이도 : Silver I

알고리즘 분류 : 그래프 탐색

 

그래프가 주어지고, 루트 노드에서부터 주어진 몇 개의 리프 노드를 방문하고 돌아온다고 할 때, 순회하는 경로의 최소 길이를 구하는 문제이다.

 

 

 

경로를 예시로 하나 그려보면, 트리에는 사이클이 없기 때문에 한 번 지나간 경로는 반드시 다시 되돌아올 때 사용해야 한다.

따라서 사용되는 간선을 구하고 그 간선들의 길이의 합의 2배를 답으로 구해주면 된다.

사용되는 간선은 bool 벡터로 체크해주면 된다.

 

그렇다면 사용되는 간선은 어떻게 구할까?

간선을 리프 노드쪽에서부터 루트 노드 방향으로 단방향으로 연결하여 M개의 리프 노드에서부터 루트 노드까지 탐색을 해주며 사용되는 간선을 기록하면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

int N, M;
int adj[1001][1001] = {};
bool check[1001][1001] = {};
vector<bool> vis;

void f(int x) {
    vis[x] = true;

    for(int i=0; i<N; i++) {
        if(adj[x][i] != -1 && !vis[i]) {
            check[x][i] = true;

            f(i);
        }
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> M;

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) adj[i][j] = -1;

    for(int i=0; i<N-1; i++) {
        int a, b, c; cin >> a >> b >> c;

        adj[b][a] = c;
    }

    while(M--) {
        int x; cin >> x;

        vis.clear();
        vis.resize(N);

        f(x);
    }

    int ans = 0;

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            if(check[i][j]) ans += adj[i][j] * 2;

    cout << ans << "\n";
}

 

 

백준 BOJ 1068번 : 트리

문제 난이도 : Gold V

알고리즘 분류 : 그래프 탐색

 

트리가 주어지고 제거할 노드가 주어질 때, 해당 노드를 제거한 뒤 트리에 존재하는 리프 노드의 개수를 구하는 문제이다.

 

제거할 노드를 체크하고 루트 노드에서 탐색을 돌려서 adj.size() == 0인 노드를 찾아주면 우선 기존의 리프 노드는 찾을 수 있다.

그 다음 제거할 노드를 유일한 자식으로 가지고 있는 노드 역시 새로운 리프 노드가 되는데 이것은 자식 노드의 개수가 1이고 그 노드가 지울 노드인지를 확인해주면 된다.

또한 이 문제에서는 루트 노드가 지워질 수도 있으므로 예외 처리를 해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<bool> vis;
int root, del, ans = 0;

void f(int x) {
    vis[x] = true;

    if(adj[x].size() == 0) {
        ans++;
        return;
    }
    if(adj[x].size() == 1 && adj[x][0] == del) {
        ans++;
        return;
    }

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(vis[y] || y == del) continue;

        f(y);
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    adj.resize(N);
    for(int i=0; i<N; i++) {
        int x; cin >> x;

        if(x == -1) {
            root = i;
            continue;
        }

        adj[x].push_back(i);
    }

    cin >> del;

    vis.resize(N);

    if(root != del) f(root);

    cout << ans << "\n";
}

 

 

백준 BOJ 2660번 : 회장뽑기

문제 난이도 : Gold V

알고리즘 분류 : 그래프 탐색

 

문제를 요약하면 주어진 그래프에서, 모든 노드에 도달하는 거리가 가장 작은 노드의 수와 그 거리, 그리고 그 노드의 번호들을 구하는 문제이다.

 

N의 크기가 50 이하로 아주 작으므로, 모든 노드에 대해 BFS를 수행하여 그 최대 거리를 직접 구해도 된다.

따라서 벡터에 모든 노드에 대한 최장 거리 노드의 거리를 구해주고, 그들 중 최솟값을 구해 그 최솟값과 동일한 최대 거리를 가지는 노드들의 개수와 번호를 구해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<vector<int>> adj(N+1);

    while(true) {
        int a, b; cin >> a >> b;
        if(a == -1 && b == -1) break;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> u(N+1);

    for(int i=1; i<=N; i++) {
        vector<int> dis(N+1, -1);
        dis[i] = 0;

        queue<int> q;
        q.push(i);

        while(!q.empty()) {
            int x = q.front();
            q.pop();

            for(int j=0; j<adj[x].size(); j++) {
                int y = adj[x][j];

                if(dis[y] != -1) continue;

                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }

        int Max = 0;
        for(int j=1; j<=N; j++)
            Max = max(Max, dis[j]);

        u[i] = Max;
    }

    int Min = INT_MAX;
    for(int i=1; i<=N; i++)
        Min = min(Min, u[i]);

    vector<int> ans;
    for(int i=1; i<=N; i++)
        if(u[i] == Min) ans.push_back(i);

    cout << Min << " " << ans.size() << "\n";
    for(int i=0; i<ans.size(); i++) cout << ans[i] << " ";
    cout << "\n";
}

 

 

백준 BOJ 24542번 : 튜터-튜티 관계의 수

문제 난이도 : Silver I

알고리즘 분류 : 그래프 탐색

 

문제를 요약하면 그래프의 각 component에서 노드를 하나씩 고르는 경우의 수를 구하는 문제이다.

 

모든 component의 연결성을 파악한 뒤 각각의 component의 노드 수를 구하여 그들의 곱을 구하면 된다.

나의 경우에는 BFS로 구현하여 visit 여부를 체크해준 뒤 cnt를 세주었다.

매 탐색이 끝날 때마다 vector에 cnt 값을 push_back 한 뒤 마지막에 모두 곱해주는 방식을 사용하였다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<vector<int>> adj(N+1);

    while(M--) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> v;
    vector<bool> vis(N+1);

    for(int i=1; i<=N; i++) {
        if(vis[i]) continue;

        int cnt = 0;

        queue<int> q;
        q.push(i);

        vis[i] = true;
        cnt++;

        while(!q.empty()) {
            int x = q.front();
            q.pop();

            for(int j=0; j<adj[x].size(); j++) {
                int y = adj[x][j];

                if(!vis[y]) {
                    q.push(y);

                    vis[y] = true;
                    cnt++;
                }
            }
        }

        v.push_back(cnt);
    }

    int ans = 1;

    for(int i=0; i<v.size(); i++) ans = (ans * v[i]) % (int)(1e9 + 7);

    cout << ans << "\n";
}

 

 

백준 BOJ 21937번 : 작업

문제 난이도 : Silver I

알고리즘 분류 : 그래프 탐색

 

어떤 일을 하기 위해서 먼저 해야하는 일의 번호 쌍이 주어질 때, K번 일을 하기 위해서 반드시 먼저 선행되어야 하는 일의 수를 구하는 문제이다.

 

그래프의 연결을 반대로 수행한 뒤, K번 노드에서부터 탐색을 하여 도달할 수 있는 노드의 수를 구해주면 그것이 답이 된다.

다만 K번 노드는 제외해야 하므로 구한 cnt에서 1을 빼주어야 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<bool> vis;

void f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(!vis[y]) f(y);
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    adj.resize(N+1);

    while(M--) {
        int a, b; cin >> a >> b;

        adj[b].push_back(a);
    }

    int K; cin >> K;

    vis.resize(N+1);

    f(K);

    int ans = 0;
    for(int i=1; i<=N; i++)
        if(vis[i] && i != K) ans++;

    cout << ans << "\n";
}

 

 

백준 BOJ 2589번 : 보물섬

문제 난이도 : Gold V

알고리즘 분류 : 그래프 탐색

 

육지와 바다로 이루어진 2차원 배열이 주어질 때, 두 육지 지점 사이의 거리가 가장 먼 곳을 찾아 그 거리를 구하는 문제이다. (물론 바다로 분리된 두 지점은 대상에서 제외된다.)

 

N, M이 모두 50 이하로 아주 작기 때문에 모든 육지 위의 지점에 대해 BFS를 수행하여 그들 중 최대 거리를 구하여 출력해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<vector<char>> v(N, vector<char>(M));
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) cin >> v[i][j];

    int ans = 0;

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) {
            if(v[i][j] != 'L') continue;

            vector<vector<int>> dis(N, vector<int>(M, -1));
            dis[i][j] = 0;

            queue<pair<int, int>> q;
            q.push({i, j});

            while(!q.empty()) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();

                int dx[4] = {1, -1, 0, 0};
                int dy[4] = {0, 0, 1, -1};

                for(int i=0; i<4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                    if(v[nx][ny] != 'L' || dis[nx][ny] != -1) continue;

                    dis[nx][ny] = dis[x][y] + 1;
                    q.push({nx, ny});
                }
            }

            for(int i=0; i<N; i++)
                for(int j=0; j<M; j++)
                    ans = max(ans, dis[i][j]);
        }

    cout << ans << "\n";
}

 

 

백준 BOJ 24237번 : Archipelago

문제 난이도 : Silver I

알고리즘 분류 : 그래프 탐색

 

섬들의 위치가 주어지고, 거리가 M 이하인 섬 사이만 이동할 수 있을 때, 몇 개의 섬을 거쳐 서로 이동할 수 있는 섬들의 개수가 많은 순서대로 섬의 번호를 출력하는 문제이다.

 

섬의 거리에 따라 거리가 M 이하이면 간선을 연결해주고, 그래프 탐색을 통해 각 섬에서 몇 개의 섬에 도달할 수 있는지를 구해준다.

이 때 탐색 자체를 N번 반복할 경우 시간 초과가 발생하므로, 한 번 방문한 그룹은 다시 방문하지 않도록 하자.

나의 경우에는 탐색 후 그 그룹의 모든 노드에 cnt를 기록하고, 어떤 노드의 cnt 값이 0이 아니면 그 노드는 skip 하는 방식으로 구현하였다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<bool> vis;

void f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(!vis[y]) f(y);
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<pair<int, int>> v(N+1);
    for(int i=1; i<=N; i++) cin >> v[i].first >> v[i].second;

    adj.resize(N+1);

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++) {
            int d = pow(abs(v[i].first - v[j].first), 2) + pow(abs(v[i].second - v[j].second), 2);

            if(d <= M*M) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }

    vector<pair<int, int>> u(N+1);
    for(int i=1; i<=N; i++) u[i].second = i;

    for(int i=1; i<=N; i++) {
        if(u[i].first != 0) continue;

        vis.clear();
        vis.resize(N+1);

        f(i);

        int cnt = 0;

        for(int j=1; j<=N; j++)
            if(vis[j]) cnt++;

        for(int j=1; j<=N; j++)
            if(vis[j]) u[j].first = cnt;
    }

    sort(u.begin()+1, u.end(), greater<pair<int, int>>());

    for(int i=1; i<=N; i++) cout << u[i].second << " ";
    cout << "\n";
}

 

 

백준 BOJ 24780번 : Kitten on a Tree

문제 난이도 : Silver I

알고리즘 분류 : 그래프 탐색

 

그래프가 주어지고 branch 노드가 주어질 때, 해당 노드에서 루트 노드까지 도달하는 경로를 구하는 문제이다.

 

각 간선을 역방향으로 연결하여 주어진 노드에서부터 그래프 탐색을 수행해주면 된다.

역방향으로 연결했기 때문에 각 노드가 이동할 수 있는 간선은 1개뿐이다.

줄마다 노드의 개수를 알려주지 않기 때문에 문자열로 입력받아 파싱하여 풀어야 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int K; cin >> K;
    cin.ignore();

    vector<vector<int>> adj(101);

    while(true) {
        string str; getline(cin, str);
        if(str == "-1") break;

        string num = "";
        int cur = 0;

        while(str[cur] != ' ') {
            num += str[cur];
            cur++;
        }

        int a = stoi(num);

        num = "";

        for(int i=cur+1; i<str.length(); i++) {
            if(str[i] != ' ') num += str[i];
            else {
                int b = stoi(num);
                adj[b].push_back(a);

                num = "";
            }
        }
        adj[stoi(num)].push_back(a);
    }

    queue<int> q;
    q.push(K);

    while(!q.empty()) {
        int x = q.front();
        q.pop();

        cout << x << " ";

        for(int i=0; i<adj[x].size(); i++) {
            q.push(adj[x][i]);
        }
    }
    cout << "\n";
}

 

 

백준 BOJ 5014번 : 스타트링크

문제 난이도 : Gold V

알고리즘 분류 : BFS

 

위로 U층 또는 아래로 D층씩만을 이동하여 출발층에서 도착층으로 이동하는 최소 횟수를 구하는 문제이다.

 

층의 제한이 100만 이하이므로 상태를 배열에 모두 저장할 수 있다.

따라서 다음과 같이 BFS로 풀이가 가능하다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, S, G, U, D; cin >> N >> S >> G >> U >> D;

    vector<int> dis(N+1, -1);
    dis[S] = 0;

    queue<int> q;
    q.push(S);

    while(!q.empty()) {
        int x = q.front();
        q.pop();

        if(x == G) {
            cout << dis[G] << "\n";
            return 0;
        }

        if(x+U <= N && dis[x+U] == -1) {
            dis[x+U] = dis[x] + 1;
            q.push(x+U);
        }
        if(x-D >= 1 && dis[x-D] == -1) {
            dis[x-D] = dis[x] + 1;
            q.push(x-D);
        }
    }

    cout << "use the stairs\n";
}

 

 

백준 BOJ 5558번 : チーズ (Cheese)

문제 난이도 : Gold V

알고리즘 분류 : BFS

 

N x M 크기의 배열에서 S에서 출발하여 1, 2, .. 순서대로 도달한 뒤 K까지 도달하는 최단 경로의 길이를 구하는 문제이다.

 

S에서 1, 1에서 2, 2에서 3, ... 의 순서대로 K-1에서 K까지 BFS를 K번 수행해주면 된다.

매 BFS마다 벡터와 큐를 초기화 해주어야 한다.

char(i + '0')과 같은 표현을 이용하면 반복문 내에서 출발 지점과 도착 지점의 문자를 처리할 수 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M, K; cin >> N >> M >> K;

    vector<vector<char>> v(N, vector<char>(M));

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) cin >> v[i][j];

    int ans = 0;

    for(int k=1; k<=K; k++) {
        char b, e;
        if(k == 1) b = 'S', e = '1';
        else b = char(k - 1 + '0'), e = char(k + '0');

        vector<vector<int>> dis(N, vector<int>(M, -1));
        queue<pair<int, int>> q;

        int ex, ey;

        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++) {
                if(v[i][j] == b) {
                    dis[i][j] = 0;
                    q.push({i, j});
                }
                else if(v[i][j] == e) {
                    ex = i;
                    ey = j;
                }
            }

        while(!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if(x == ex && y == ey) {
                ans += dis[ex][ey];
                break;
            }

            int dx[4] = {1, -1, 0, 0};
            int dy[4] = {0, 0, 1, -1};

            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if(v[nx][ny] == 'X' || dis[nx][ny] != -1) continue;

                dis[nx][ny] = dis[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 1245번 : 농장 관리

문제 난이도 : Gold V

알고리즘 분류 : BFS

 

N x M 크기의 배열이 주어질 때, 산봉우리와 인접(x, y 좌표가 1 이하의 차이를 가지는)한 점들의 높이는 모두 산봉우리 이하라고 정의할 때 산봉우리의 수를 구하는 문제이다.

 

주어진 배열에서 가장 큰 값을 찾아주고, 그 값에서 BFS를 수행하면서 해당 칸들을 체크하면서 내려온다.

한 번의 BFS 탐색이 하나의 봉우리이다.

이제 체크되지 않은 칸들 중에서 가장 큰 값에서 BFS를 하고, 이러한 과정을 반복하면 반복 횟수만큼이 산봉우리의 개수가 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

int N, M;
vector<vector<int>> v;
vector<vector<bool>> vis;

void f(int x, int y) {
    vis[x][y] = true;

    int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

    for(int i=0; i<8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if(vis[nx][ny] || v[nx][ny] > v[x][y]) continue;

        f(nx, ny);
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> M;

    v.resize(N, vector<int>(M));

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) cin >> v[i][j];

    vis.resize(N, vector<bool>(M));
    int ans = 0;

    while(true) {
        int Max = -1;

        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                if(!vis[i][j]) Max = max(Max, v[i][j]);

        if(Max == -1) break;

        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                if(!vis[i][j] && v[i][j] == Max) {
                    f(i, j);

                    ans++;
                }
    }

    cout << ans << "\n";
}