Murra Blog

BOJ 9466번 텀 프로젝트 문제

DFS를 통해서 푸는건데, 생각보다 복잡했다.

이미 팀에 속한 애인지 확인해야한다.

혼자 잘 안풀려서 도움을 받아서 풀었다.

9466.cpp

#include <bits/stdc++.h>
using namespace std;
bool visited[100001];
bool belong[100001];
int stu[100001];
int memCount;
void solve();
void DFS(int);
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}
void solve() {
    int n;
    cin >> n;
    memset(visited, 0, sizeof(visited));
    memset(belong, 0, sizeof(belong));
    memCount = 0;
    for (int i = 1; i <= n; i++) {
        cin >> stu[i];
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            DFS(i);
        }
    }
    cout << n - memCount << '\n';
}
void DFS(int n) {
    visited[n] = true;
    int next = stu[n];
    if (visited[next]) {
        if (!belong[next]) {
            for (int i = next; i != n; i = stu[i]) {
                memCount++;
            }
            memCount++;
        }
    } else {
        DFS(stu[n]);
    }
    belong[n] = true;
}

BOJ 2583번 영역 구하기 문제

DFS, BFS 모두 가능한 문제다. 아마.

큐 넣기가 더 귀찮을거 같아서 DFS로 풀었는데, 나는 더 간단한 코드를 보여주기 위해 더 복잡한 코드를 만드는 거 같다. 그래서 이거 푸는데 시간이 생각보다 많이 걸렸다.

앞으로 간결하고 빠르게 짤 수 있는 코딩을 연습해야겠다.

2583.cpp

#include <bits/stdc++.h>
using namespace std;
bool range[101][101];
bool visited[101][101];
int M, N, K;
void DFS(int y, int x, int &area) {
    visited[y][x] = true;
    area++;

    // -1 0 / +1 0 / 0 -1 / 0 +1
    vector<pair<int, int> > wsad;
    wsad.push_back({-1, 0});
    wsad.push_back({+1, 0});
    wsad.push_back({0, -1});
    wsad.push_back({0, +1});

    for (int i = 0; i < 4; i++) {
        int nextY = y + wsad[i].first;
        int nextX = x + wsad[i].second;
        bool yCheck = (nextY >= 0) && (nextY < M);
        bool xCheck = (nextX >= 0) && (nextX < N);
        if (yCheck && xCheck) {
            if (!range[nextY][nextX] && !visited[nextY][nextX])
                DFS(nextY, nextX, area);
        }
    }
}

int main() {
    vector<int> area;
    cin >> M >> N >> K;
    while (K--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int i = y1; i < y2; i++) {
            for (int j = x1; j < x2; j++) {
                range[i][j] = true;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            // 네모 영역이 아니면서 방문하지 않은 곳
            if (!range[i][j] && !visited[i][j]) {
                int ar = 0;
                DFS(i, j, ar);
                area.push_back(ar);
            }
        }
    }
    sort(area.begin(), area.end());
    cout << area.size() << '\n';
    for (auto i : area) {
        cout << i << " ";
    }
}

BOJ 2331번 반복수열 문제

이 문제는 DFS로 풀었다.

각 자리 숫자를 P 제곱한 후 더한게 다음 숫자가 되는 방식인데, 중간에 계속해서 반복되는 구간이 나타난다.

그 구간에 포함되지 않는 숫자들의 갯수를 구하는 문제이다.

자꾸 pow(5, 2)를 24로 출력해서 뭐가 잘못됐나 했는데 pow() 함수의 return type이 실수형이었다.

그래서 반올림해서 정수형으로 변환했다.

2331.cpp

#include <bits/stdc++.h>
using namespace std;
int result;
int visitCount[1000000];

int mult(int A, int P) {
    int next = 0;
    while (A > 0) {
        next += (int)floor(pow(A % 10, P)+0.5);
        A /= 10;
    }
    return next;
}

void DFS(int A, int P) {
    visitCount[A]++;
    if (visitCount[A] > 2) {
        return;
    }
    DFS(mult(A, P), P);
}

int main() {
    int A, P;
    cin >> A >> P;
    DFS(A, P);

    for (int i = 0; i < 100000; i++) {
        if (visitCount[i] == 1) {
            result++;
        }
    }

    cout << result;
}