백준 2638 치즈 (c++) : 피너클

https://www.acmicpc.net/problem/2638

2638번: 치즈

귀찮은 구현문제다.

치즈를 찾은 뒤 치즈가 외부 공기와 접촉하는지 확인 해야한다. 치즈의 위, 아래, 왼쪽, 오른쪽을 각각 확인할거다.

int n, m;
int map[101][101];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
queue<pair<int, int>> q;

입력받을 값들이다. map은 모눈종이, q는 치즈의 위치를 저장한다.

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) q.push({ i, j });
	}
}

값을 입력받고 만약 입력 받은 값이 1이라면 (치즈라면) q에 위치를 집어넣는다.

int time = 0;
while (!q.empty()) {
	time++;
	vector<pair<int, int>> v;
	int qsize = q.size();

int time은 지난 시간을 나타낸다.

bfs를 이용할것이다. q가 차있는동안 반복문은 진행한다.

time에 1을 더하고 vector<pair<int, int>> v를 선언한다. v에는 이번에 사라질 치즈를 저장한다.

qsize에 현재 q사이즈를 저장한다.

	while (qsize-- > 0) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
			
		int air = 0;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (map[ny][nx] != 1 && isOut(ny, nx)) {
				air++;
			}
		}
		if (air >= 2) v.push_back({ y, x });
		else q.push({ y, x });
	}

qsize만큼 반복문을 돌린다.

현재 q앞에 있는 치즈를 꺼낸뒤 q를 pop한다.

그후 4방향을 확인하면서 map[ny][nx]가 치즈가 아니고 외부와 접촉해 있다면 air++를 해준다.

4방향을 확인한 다음 만약 air가 2 이상이라면 (외부와 2 이상 접촉해있다면) v에 치즈 위치를 넣어준다.

air가 2 이상이 아니라면 q에 다시 값을 집어넣어준다.

 

이제 isOut함수를 확인한다.

bool isOut(int y, int x) {
	bool visited[101][101];
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	q.push({ y, x });
	visited[y][x] = true;

isOut함수도 일반적인 bfs와 똑같이 진행한다. 기본 준비를 한다.

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		if (y == 0 || x == 0 || y == n - 1 || x == m - 1) return true;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				if (!visited[ny][nx] && map[ny][nx] == 0) {
					visited[ny][nx] = true;
					q.push({ ny, nx });
				}
			}
		}
	}
	return false;
}

일반적인 bfs다. 만약 현재 위치가 모눈종이의 끝이라면 바로 true를 리턴한다.

그후 현재 다음 위치를 확인하며 방문하지 않았고 비어있는 공간이면 q에 집어넣어준다.

반복문을 다 돌렸는데도 외부와 접촉하지 못했다면 false를 리턴한다.

	for (int i = 0; i < v.size(); i++) map[v[i].first][v[i].second] = 0;
}
cout << time << endl;

그후 main함수에서는 v 안에 있는 모든 위치의 치즈들을 없애주고 반복문이 끝나면 time을 출력한다.

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

int n, m;
int map[101][101];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
queue<pair<int, int>> q;

bool isOut(int y, int x) {
	bool visited[101][101];
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	q.push({ y, x });
	visited[y][x] = true;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		if (y == 0 || x == 0 || y == n - 1 || x == m - 1) return true;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				if (!visited[ny][nx] && map[ny][nx] == 0) {
					visited[ny][nx] = true;
					q.push({ ny, nx });
				}
			}
		}
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.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) q.push({ i, j });
		}
	}
	int time = 0;
	while (!q.empty()) {
		time++;
		vector<pair<int, int>> v;
		int qsize = q.size();
		while (qsize-- > 0) {
			int y = q.front().first;
			int x = q.front().second;
			q.pop();

			int air = 0;
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (map[ny][nx] != 1 && isOut(ny, nx)) {
					air++;
				}
			}
			if (air >= 2) v.push_back({ y, x });
			else q.push({ y, x });
		}
		for (int i = 0; i < v.size(); i++) map[v[i].first][v[i].second] = 0;
	}
	cout << time << endl;
}

전체코드다.