[백준] 2638 치즈

2638번: 치즈

 

www.acmicpc.net

풀이

치즈 외부 공기와 접촉한 치즈들을 체크하는 것이 관건인 문제이다.
문제에 모는종이의 맨 가장자리에는 치즈가 놓이지 않는다 명시되어 있으므로 (0, 0)은 비어있는 칸임을 알 수 있다. 그래서 (0,0)에서 BFS로 탐색하여 외부 공기와 접촉한 치즈를 체크하여 해결하였다.

BFS 탐색을 마쳤을 때 2차원 배열 visited의 값이 2 이상인 경우에는 외부 공기와 접축한 치즈라는 의미이므로 제거하였다.

코드

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n, m, cnt;
int map[101][101], visited[101][101];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

void checkOutline() {
    for (int i = 0; i < n; i++) fill(visited[i], visited[i] + m, 0);
    queue<pair<int, int>> q;
    q.push({ 0, 0 });
    visited[0][0] = 1;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1) continue;
            if (map[ny][nx] == 1) visited[ny][nx]++;
            if (visited[ny][nx] == 0 && map[ny][nx] == 0) {
                q.push({ nx, ny });
                visited[ny][nx] = 1;
            }
        }
    }
}

void removeCheese() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visited[i][j] > 1) {
                map[i][j] = 0;
                cnt--;
            }
        }
    }
}

int solve() {
    int time = 0;
    while (cnt > 0) {
        checkOutline();
        removeCheese();
        time++;
    }
    return time;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1) cnt++;
        }
    }
    cout << solve() << '\n';
    return 0;
}

Java

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n, m, cnt = 0;
    static int[][] map;
    static int[][] visited;
    static StringTokenizer st;
    static BufferedReader br;
    static BufferedWriter bw;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) {
        input();
        solve();
    }

    public static void solve() {
        int time = 0;
        while (cnt > 0) {
            checkOutline();
            removeCheese();
            time++;
        }
        try {
            bw.write(String.valueOf(time));
            bw.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void removeCheese() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j] > 1) {
                    map[i][j] = 0;
                    cnt--;
                }
            }
        }
    }

    public static void checkOutline() {
        for (int i = 0; i < n; i++) Arrays.fill(visited[i], 0);
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        visited[0][0] = 1;

        while (!q.isEmpty()) {
            Point cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1) continue;
                if (map[ny][nx] == 1) visited[ny][nx]++;
                if (visited[ny][nx] == 0 && map[ny][nx] == 0) {
                    q.add(new Point(nx, ny));
                    visited[ny][nx] = 1;
                }
            }
        }
    }

    public static void input() {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
            st = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            map = new int[n][m];
            visited = 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());
                    if (map[i][j] == 1) cnt++;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}