Murra Blog

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';
    }
}

BOJ 4963번 섬의개수 문제

BFS로 붙어있는거 체크를 하는데, 2667번 단지번호붙이기와 거의 같은데, 대각선 방향이 추가된다.

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';
    }
}

BOJ 16397번 탈출 문제

2018 홍익대학교 컴퓨터공학과 코딩대회 D번 문제이다.

또 문제를 잘 못 봤다. 제일 높은 자리수 1을 빼는게 각 자리를 비교해서 가장 큰 수를 뺴는 걸로 생각했다.

왜 더 어렵게 생각해서 구현도 복잡하고 시간도 더 낭비했는지..

이런 것도 다 실력이니 이런 실수를 줄이는 노력을 해야겠다.

문제는 BFS로 풀면 된다.

16397.cpp

#include <bits/stdc++.h>
using namespace std;
bool visited[100000];
int po(int n) {
    int nn = 1;
    for (int i = 0; i < n; i++) {
        nn *= 10;
    }
    return nn;
}
int B(int i) {
    if (i == 0) {
        return i;
    }
    int originI = i * 2;
    i = originI;
    int t = 0;
    while (i > 0) {
        t++;
        i /= 10;
    }
    originI -= po(t - 1);
    return originI;
}

int main() {
    int n, t, g;
    cin >> n >> t >> g;
    queue<pair<int, int> > q;
    visited[n] = true;
    q.push({n, 0});

    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if (cnt > t) {
            cout << "ANG";
            return 0;
        }
        if (now == g) {
            cout << cnt;
            return 0;
        }

        if ((now + 1 <= 99999) && !visited[now + 1]) {
            q.push({now + 1, cnt + 1});
            visited[now + 1] = true;
        }
        int next = B(now);
        if ((now * 2 <= 99999) && !visited[next]) {
            q.push({next, cnt + 1});
            visited[next] = true;
        }
    }
    cout << "ANG";
}

BOJ 2251번 물통 문제

BFS로 풀었다.

C에서 B, A로 담는 경우, B에서 A, C로 담는 경우, A에서 B, C로 주는 경우를 고려하면 된다.

물통이 용량을 모두 수용할 수 있는지 여부를 체크해줘야 한다.

항상 이런거 짤때 실수를 해서 고치느라 애먹었다.

답을 출력할 때 중복 값이 나와서 set에 담아서 출력했다.

2251.cpp

#include <bits/stdc++.h>
using namespace std;
bool visited[201][201][201];
struct Water {
    int a;
    int b;
    int c;
};
int main() {
    int A, B, C;
    cin >> A >> B >> C;
    set<int> ans;
    queue<Water> q;
    q.push({0, 0, C});

    while (!q.empty()) {
        int nowA = q.front().a;
        int nowB = q.front().b;
        int nowC = q.front().c;
        q.pop();
        if (visited[nowA][nowB][nowC])
            continue;
        visited[nowA][nowB][nowC] = true;
        // A가 0일때의 C의 용량을 담는다.
        if (nowA == 0) {
            //ans.push_back(nowC);
            ans.insert(nowC);
        }
        // case 1) C->B
        if (nowB + nowC > B) {
            q.push({nowA, B, nowB + nowC - B});
        } else {
            q.push({nowA, nowB + nowC, 0});
        }
        // case 2) C->A
        if (nowA + nowC > A) {
            q.push({A, nowB, nowA + nowC - A});
        } else {
            q.push({nowA + nowC, nowB, 0});
        }
        // case 3) B->A
        if (nowA + nowB > A) {
            q.push({A, nowA + nowB - A, nowC});
        } else {
            q.push({nowA + nowB, 0, nowC});
        }
        // case 4) B->C
        if (nowB + nowC > C) {
            q.push({nowA, nowB + nowC - C, C});
        } else {
            q.push({nowA, 0, nowB + nowC});
        }
        // case 5) A->B
        if (nowA + nowB > B) {
            q.push({nowA + nowB - B, B, nowC});
        } else {
            q.push({0, nowA + nowB, nowC});
        }
        // case 6) A->C
        if (nowA + nowC > C) {
            q.push({nowA + nowC - C, nowB, C});
        } else {
            q.push({0, nowB, nowA + nowC});
        }
    }
    set<int>::iterator iter;
    for (iter = ans.begin(); iter != ans.end(); iter++) {
        cout << *iter << " ";
    }
}

BOJ 1697번 숨바꼭질 문제

BFS 돌다리 문제랑 거의 같다.

-1, +1, 2*현재 자리로 움직일 수 있다.

인덱스 체크가 필요하다.

1697.cpp

#include <bits/stdc++.h>
using namespace std;
int N, K;
bool visited[100001];
int main() {
    cin >> N >> K;

    queue<pair<int, int> > q;
    visited[N] = true;
    q.push({N, 0});
    while (!q.empty()) {
        int position = q.front().first;
        int count = q.front().second;
        q.pop();

        if (position == K) {
            cout << count;
            return 0;
        }
        if (position - 1 >= 0 && !visited[position - 1]) {
            visited[position - 1] = true;
            q.push({position - 1, count + 1});
        }
        if (position + 1 <= 100000 && !visited[position + 1]) {
            visited[position + 1] = true;
            q.push({position + 1, count + 1});
        }
        if (position * 2 <= 100000 && !visited[position * 2]) {
            visited[position * 2] = true;
            q.push({position * 2, count + 1});
        }
    }
}