BOJ 2636번: 치즈

1. 문제

문제 바로가기> BOJ 2636번: 치즈

2636번: 치즈

 

2. 풀이

치즈의 구멍인지, 빈칸인지 확이하기 위해서 4꼭지점에서 BFS 탐색을 시작해 주는게 핵심이다!

 

2.0.1. C++

      

      

      

    
    

      <cpp />
    
#include <iostream>
#include <queue>
#define MAX 101
#define EMPTY 0
#define CHEESE 1
using namespace std;

struct POS
{
    int r, c;
};

int R, C;
int total = 0;
int map[MAX][MAX];
bool visited[MAX][MAX];
bool tmp_visisted[MAX][MAX];
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void input()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> map[i][j];
            total += map[i][j]; // 치즈 조각이 놓여 있는 칸 수
        }
    }
}

void check_not_cheese(queue<POS> &q)
{
    while (!q.empty())
    {
        int r = q.front().r;
        int c = q.front().c;
        q.pop();

        for (int d = 0; d < 4; d++)
        {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C)
                continue;
            if (map[nr][nc] == CHEESE || visited[nr][nc])
                continue;
            visited[nr][nc] = true;
            q.push({nr, nc});
        }
    }
}

void melted_cheese(queue<POS> &q)
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
            tmp_visisted[i][j] = visited[i][j];
    }

    for (int r = 1; r < R - 1; r++)
    {
        for (int c = 1; c < C - 1; c++)
        {
            if (map[r][c] == EMPTY)
                continue;
            for (int d = 0; d < 4; d++)
            {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (tmp_visisted[nr][nc])
                {
                    visited[nr][nc] = true;
                    map[r][c] = EMPTY;
                    q.push({nr, nc});
                    break;
                }
            }
        }
    }
}

void solution()
{	
	// 4 꼭짓점에서 BFS 시작
    int sy[] = {0, 0, R - 1, R - 1};
    int sx[] = {0, C - 1, 0, C - 1};

    queue<POS> q;
    for (int i = 0; i < 4; i++)
    {
        q.push({sy[i], sx[i]});
        visited[sy[i]][sx[i]] = true;
    }

    for (int t = 1;; t++)
    {
        check_not_cheese(q);
        melted_cheese(q);
        if (q.size() == total)
        {
            cout << t << "\n"
                 << total;
            return;
        }
        else
            total -= q.size();
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    input();
    if (total)
        solution();
    else
        cout << 0 << "\n"
             << 0;
}

 

2.0.2. JAVA

      

      

      

    
    

      <java />
    
import java.io.*;
import java.util.*;

public class Main {
	
	static final int[] dy = {-1,1,0,0};
	static final int[] dx = {0,0,-1,1};
	
	static int R, C;
	static int cheeseCnt= 0;
	static boolean[][] map, visited;
	static ArrayDeque<int[]> q = new ArrayDeque<>();
	
	private static int solution() {
		int res = 0; // 녹은 치즈
		visited = new boolean[R][C];
		ArrayDeque<int[]> next = new ArrayDeque<>();
		
		while(!q.isEmpty()) {
			int y = q.peek()[0];
			int x = q.peek()[1];
			q.poll();
			
			for(int d=0; d<4; d++) {
				int ny = y+dy[d];
				int nx = x+dx[d];
				if(ny<0 || ny>=R || nx<0 || nx>=C || visited[ny][nx]) continue;
				visited[ny][nx] = true;
				if(map[ny][nx]) { // cheese
					map[ny][nx] = false;
					next.offer(new int[] {ny, nx});
					res++;
				}
				else q.offer(new int[] {ny, nx});
			}
		}
		q = next;
		return res;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// input
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new boolean[R][C];
		
		for(int i=0; i<R; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<C; j++) {
				map[i][j] = (Integer.parseInt(st.nextToken())==0?false:true);
				if(map[i][j]) cheeseCnt++;
			}
		}

		// solution: 가장 자리에서 시작
		q.offer(new int[] {0, 0});
		q.offer(new int[] {0, C-1});
		q.offer(new int[] {R-1, 0});
		q.offer(new int[] {R-1, C-1});
		
		int meltTime=0, lastPiece=0;
		while(true) {
			if(cheeseCnt==0) break;
			cheeseCnt-=solution();
			lastPiece = q.size();
			meltTime++;
		}
		
		// output
		System.out.println(meltTime);
		System.out.println(lastPiece);
	}
}