[백준 2636번 / C++] 치즈

1. 사각형의 테두리는 0으로 되어있다.

2. {0,0}에서 bfs를 돌린다. 

3. {ny,nx} 좌표를 가지고 있는 map의 값이 1이라면 벽이라고 생각을 하고 뚫고 가진 못하지만 방문 처리만 해주자. 

4. 상,하,좌,우로 연결된 길을 모두 탐색했다면 visited에 1로 기록되어있는 map을 0으로 갱신하자. (즉, 벽을 허물라)

5. map에서 갱신 된 내용이 없으면 리턴하고 그렇지 않다면 다시 {0,0}에서 bfs를 돌린다.   

#include <iostream>
#include <queue>
#include <tuple>
#include <memory.h>
using namespace std;
queue<pair<int, int>>q; 
int dx[4] = { 0,0,1,-1 }; 
int dy[4] = { 1,-1,0,0 }; 
int map[100][100]; 
int visited[100][100]; 
int m, n, check, bfs_cnt, last_area; 
void bfs() {
	visited[0][0] = 1; 
	while (!q.empty()) {
		int x, y; 		
		tie(y, x) = q.front(); 
		q.pop(); 
		if (map[y][x] == 0) {
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
				if (visited[ny][nx])continue;
				if (map[ny][nx] == 0) {	
					visited[ny][nx] = 1;
					q.push({ ny, nx });
				}
				if (map[ny][nx] == 1) {
					visited[ny][nx] = 1; 
				}
			}
		}
	}
	int cnt = 0; 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && visited[i][j] == 1) {
				map[i][j] = 0;				
				cnt++;
			}
		}
	}
	if (cnt != 0) {
		memset(visited, 0, sizeof(visited));
		last_area = cnt;
		q.push({ 0,0 });
		bfs_cnt++;
		bfs();
	}
	else  return; 
}
int main() {
	cin >> m >> n; 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j]; 
		}
	}
	q.push({ 0,0 }); 
	bfs(); 
	cout << bfs_cnt << endl; 
	cout << last_area << endl; 	
}

채점 현황