[BaekJoon] 2638번 - 치즈 [Java][C++]

문제 링크

---

1. 문제 풀이

치즈는 외부 공기와 두 변이상 접촉한 경우 한 시간 후에 사라진다. 이때 모눈종이의 가장자리는 치즈가 놓이지 않는 것으로 가정하므로 무한 루프를 돌며 모눈종이 가장자리 중 임의의 좌표에서 BFS를 통해 두 번 이상 치즈가 존재하는 것으로 판단된 좌표들을 찾아서 녹여주는 방식으로 해결했다.

치즈가 존재하는 좌표를 발견하면 먼저 마킹을 해주고 이후 치즈가 존재하면서 마킹이 된 좌표면 배열에 담았다가 해당 좌표의 치즈를 녹여줬다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int time = 0;
        while (true) {
            boolean isChanged = bfs(N, M, map);

            if (!isChanged) break;
            time++;
        }

        System.out.println(time);
    }

    static boolean bfs(int N, int M, int[][] map) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});

        boolean[][] visited = new boolean[N][M];
        visited[0][0] = true;

        boolean[][] check = new boolean[N][M];
        List<int[]> checkList = new ArrayList<>();

        while (!q.isEmpty()) {
            int[] node = q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = node[0] + dr[d];
                int nc = node[1] + dc[d];

                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                if (visited[nr][nc]) continue;
                if (map[nr][nc] == 1) {
                    if (check[nr][nc]) {
                        checkList.add(new int[]{nr, nc});
                    } else {
                        check[nr][nc] = true;
                    }
                    continue;
                }

                q.offer(new int[]{nr, nc});
                visited[nr][nc] = true;
            }
        }

        if (checkList.isEmpty()) return false;

        for (int[] pos : checkList) {
            map[pos[0]][pos[1]] = 0;
        }

        return true;
    }
}

2. 풀이 [C++]

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

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int n, m;
int grid[100][100];
bool visited[100][100];
bool check[100][100];

bool bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});

    memset(visited, 0, sizeof(visited));
    visited[0][0] = true;

    memset(check, 0, sizeof(check));
    vector<pair<int, int>> v;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (visited[nr][nc]) continue;
            if (grid[nr][nc] == 1) {
                if (check[nr][nc]) {
                    v.push_back({nr, nc});
                } else {
                    check[nr][nc] = true;
                }
                continue;
            }

            q.push({nr, nc});
            visited[nr][nc] = true;
        }
    }

    if (v.empty()) return false;

    for (auto [r, c] : v) {
        grid[r][c] = 0;
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    int time = 0;
    while (true) {
        bool flag = bfs();

        if (!flag) break;
        time++;
    }

    cout << time;
}

---