Murra Blog

BOJ 1717번 집합의 표현 문제

0일땐 합집합을 하고, 1일땐 같은 집합인지 확인하는 문제이다.

union-find 기본 문제였다.

1717.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXX 1000001
int parent[MAXX], n, m, check, first, second;

void _union(int, int);
int find(int);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    // 일단 자기 자신으로 초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    while (m--) {
        cin >> check >> first >> second;
        if (!check) {
            _union(first, second);
        } else {
            if (find(first) == find(second)) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }
}

void _union(int f, int s) {
    int firstParent = find(f);
    int secondParent = find(s);
    if (firstParent != secondParent)
        parent[firstParent] = secondParent;
}
int find(int i) {
    if (parent[i] == i) {
        return i;
    } else {
        return parent[i] = find(parent[i]);
    }
}

BOJ 1476번 날짜 계산 문제

일반 구현 문제이다. 15 28 19에 모두 나누어 떨어지는 수를 구하면 된다.

좀 헤맸다.

1476.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    int e, s, m;
    cin >> e >> s >> m;
    int i = 1;
    while (true) {
        if ((i - e) % 15 == 0 && (i - s) % 28 == 0 && (i - m) % 19 == 0) {
            cout << i;
            return 0;
        }
        i++;
    }
}

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 1717번 집합의 표현 문제

0일땐 합집합을 하고, 1일땐 같은 집합인지 확인하는 문제이다.

union-find 기본 문제였다.

1717.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXX 1000001
int parent[MAXX], n, m, check, first, second;

void _union(int, int);
int find(int);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    // 일단 자기 자신으로 초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    while (m--) {
        cin >> check >> first >> second;
        if (!check) {
            _union(first, second);
        } else {
            if (find(first) == find(second)) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }
}

void _union(int f, int s) {
    int firstParent = find(f);
    int secondParent = find(s);
    if (firstParent != secondParent)
        parent[firstParent] = secondParent;
}
int find(int i) {
    if (parent[i] == i) {
        return i;
    } else {
        return parent[i] = find(parent[i]);
    }
}

BOJ 7569번 토마토 문제

BFS로 풀면 된다.

7576번 토마토 코드를 베껴와서 3차원으로 수정해서 풀려고 했는데, 꼬여서 더 안됐다.

그래서 다시 짰다.

7569.cpp

#include <bits/stdc++.h>
using namespace std;
int dx[6] = {0, 0, +1, 0, 0, -1};
int dy[6] = {0, +1, 0, 0, -1, 0};
int dz[6] = {+1, 0, 0, -1, 0, 0};
int tomato[101][101][101];
int n, m, h;

struct ijk {
    int y;
    int x;
    int z;
    int day;
};

int main() {
    cin >> m >> n >> h;
    queue<ijk> q;
    int tomatoNot = 0;
    for (int z = 0; z < h; z++) {
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < m; x++) {
                cin >> tomato[y][x][z];
                if (tomato[y][x][z] == 1) {
                    q.push({y, x, z, 0});
                }
                if (tomato[y][x][z] == 0) {
                    tomatoNot++;
                }
            }
        }
    }
    int cantTomato = m * n * h - tomatoNot - q.size();
    int maxDay = 0;
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int z = q.front().z;
        int day = q.front().day;
        q.pop();

        for (int i = 0; i < 6; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            int nz = z + dz[i];
            if (ny >= 0 && ny < n && nx >= 0 && nx < m && nz >= 0 && nz < h) {
                if (tomato[ny][nx][nz] == 0) {
                    tomato[ny][nx][nz] = 1;
                    q.push({ny, nx, nz, day + 1});
                }
            }
        }
        maxDay = max(maxDay, day);
    }
    for (int z = 0; z < h; z++) {
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < m; x++) {
                if (tomato[y][x][z] == 0) {
                    cout << "-1";
                    return 0;
                }
            }
        }
    }
    cout << maxDay;
}

BOJ 7576번 토마토 문제

BFS로 풀면 된다.

7576.cpp

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int tomato[1001][1001];
int d[1001][1001];
int n, m;
int main() {
    scanf("%d %d", &m, &n);
    queue<pair<int, int> > q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &tomato[i][j]);
            d[i][j] = -1;
            if (tomato[i][j] == 1) {
                q.push({i, j});
                d[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (tomato[nx][ny] == 0 && d[nx][ny] == -1) {  // 익지 않은 토마토 이면서 방문하지 않은 곳
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            result = max(result,d[i][j]);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tomato[i][j] == 0 && d[i][j] == -1) {
                result = -1;
            }
        }
    }
    cout << result;
}

BOJ 2667번 단지번호붙이기 문제

BFS로 붙어있는거 체크를 하는데, 단지가 바뀔때마다 단지 번호를 1씩 늘려야한다.

2667.cpp

#include <bits/stdc++.h>
using namespace std;
int map_[26][26];
int countCheck[26][26];
int townNum;
int n;
int dirY[4] = {+1, -1, 0, 0};
int dirX[4] = {0, 0, -1, +1};

void BFS(int y, int x, int townNum) {
    queue<pair<int, int> > q;
    q.push({y, x});
    countCheck[y][x] = townNum;
    while (!q.empty()) {
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextY = y + dirY[i];
            int nextX = x + dirX[i];
            if (nextY >= 0 && nextY < n && nextX >= 0 && nextX < n) {
                if (map_[nextY][nextX] == 1 && countCheck[nextY][nextX] == 0) {
                    q.push({nextY, nextX});
                    countCheck[nextY][nextX] = townNum;
                }
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &map_[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_[i][j] == 1 && countCheck[i][j] == 0) {
                townNum++;
                BFS(i, j, townNum);
            }
        }
    }
    vector<vector<int> > town(25 * 25);

    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            int townIndex = countCheck[y][x];
            if (townIndex == 0) continue;
            town[townIndex].push_back(1);
        }
    }
    sort(town.begin(), town.end());

    cout << townNum << '\n';
    for (int i = 0; i < town.size(); i++) {
        if (town[i].size() == 0) continue;
        cout << town[i].size() << '\n';
    }
}