백준 BOJ 새로 나온 문제들 풀어보기 220904

백준 BOJ 25513번 : 빠른 오름차순 숫자 탐색

문제 난이도 : Gold V

알고리즘 분류 : BFS

 

주어진 5 x 5 크기의 배열에서, 특정 위치에서 시작하여 1, 2, 3, 4, 5, 6을 순서대로 방문하는 최소 경로의 길이를 구하는 문제이다. (이 때, -1은 지나갈 수 없는 칸이며 만약 순서대로 방문하는 것이 불가능하다면 -1을 출력해야 한다.)

 

BFS를 반복문으로 여러 번 사용하는 문제이다.

초기 위치에서 cur(1 ~ 6으로 반복문을 돌려준다.)를 방문하는 BFS를 구현하고, 방문이 되었다면 초기 위치를 해당 칸의 위치로 바꿔주고 다음 루프를 돌면 된다.

만약 방문이 불가능하다면 -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);

    vector<vector<int>> v(5, vector<int>(5));

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

    int si, sj; cin >> si >> sj;

    int ans = 0;

    for(int cur=1; cur<=6; cur++) {
        queue<pair<int, int>> q;
        q.push({si, sj});

        vector<vector<int>> dis(5, vector<int>(5, -1));
        dis[si][sj] = 0;

        bool check = false;

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

            if(v[x][y] == cur) {
                ans += dis[x][y];
                si = x, sj = y;

                check = true;
                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 >= 5 || ny >= 5) continue;
                if(dis[nx][ny] != -1 || v[nx][ny] == -1) continue;

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

        if(!check) {
            cout << -1 << "\n";
            return 0;
        }
    }

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

 

 

백준 BOJ 25512번 : 트리를 간단하게 색칠하는 최소 비용

문제 난이도 : Silver I

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

 

주어진 트리에 대해 각 노드를 검은색 또는 흰색으로 칠하는 비용이 주어지고, 인접한 노드는 다른 색으로 칠하려고 할 때 모든 노드를 칠하는 최소 비용을 구하는 문제이다.

 

트리이기 때문에 사이클이 없고, 따라서 하나의 노드의 색을 결정하면 모든 나머지 노드들의 색이 결정된다.

따라서 루트 노드를 검은색으로 칠하는 경우와, 흰색으로 칠하는 경우 두 가지를 구한 뒤 비교해서 최솟값을 출력해주면 된다.

 

 

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

int N;
vector<vector<int>> adj;
vector<int> v, u;
int a = 0, b = 0;

void f(int x, int pre) {
    if(pre == 0) a += v[x];
    else a += u[x];

    for(int i=0; i<adj[x].size(); i++) {
        if(pre == 0) f(adj[x][i], 1);
        else f(adj[x][i], 0);
    }
}

void g(int x, int pre) {
    if(pre == 0) b += v[x];
    else b += u[x];

    for(int i=0; i<adj[x].size(); i++) {
        if(pre == 0) g(adj[x][i], 1);
        else g(adj[x][i], 0);
    }
}

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

    cin >> N;

    adj.resize(N);

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

        adj[a].push_back(b);
    }

    v.resize(N);
    u.resize(N);

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

    f(0, 0);

    g(0, 1);

    cout << min(a, b) << "\n";
}

 

 

백준 BOJ 25516번 : 거리가 k이하인 트리 노드에서 사과 수확하기

문제 난이도 : Silver II

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

 

트리가 주어지고, 루트 노드에서 거리가 k 이하인 노드들에서만 사과를 수확할 때 그 개수를 구하는 문제이다. (각 노드의 사과 개수가 주어진다.)

 

깊이가 k 이하인 노드를 모두 방문하여 노드의 사과 개수를 답에 더해준 뒤, 답을 출력해주면 된다.

 

 

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

int N, M, ans = 0;
vector<vector<int>> adj;
vector<int> v;

void f(int x, int dep) {
    ans += v[x];

    if(dep == M) return;

    for(int i=0; i<adj[x].size(); i++) f(adj[x][i], dep+1);
}

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

    cin >> N >> M;

    adj.resize(N);

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

        adj[a].push_back(b);
    }

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

    f(0, 0);

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

 

 

백준 BOJ 25511번 : 값이 k인 트리 노드의 깊이

문제 난이도 : Silver II

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

 

트리에서 각 노드가 가지는 값이 따로 주어질 때, 값 k를 가지는 노드의 깊이를 구하는 문제이다.

 

루트 노드에서부터 재귀적으로 탐색하다가 노드 값이 k인 노드를 방문했을 때의 깊이를 답으로 저장해준다.

탐색이 끝나고 나서 답을 출력해주면 된다.

 

 

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

int N, M;
vector<vector<int>> adj;
vector<int> v;
int ans;

void f(int x, int dep) {
    if(v[x] == M) ans = dep;

    for(int i=0; i<adj[x].size(); i++) f(adj[x][i], dep+1);
}

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

    cin >> N >> M;

    adj.resize(N);

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

        adj[a].push_back(b);
    }

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

    f(0, 0);

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

 

 

백준 BOJ 25527번 : Counting Peaks of Infection

문제 난이도 : Bronze III

알고리즘 분류 : 구현

 

문제 제목 그대로 그래프의 피크의 개수를 구하는 문제이다.

 

v[i] > v[i-1]이면서 동시에 v[i] < v[i+1]인 i의 개수를 세어주면 된다.

 

 

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

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

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

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

        int ans = 0;

        for(int i=1; i<N-1; i++)
            if(v[i] > v[i-1] && v[i] > v[i+1]) ans++;

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