[백준 2636] 치즈

난이도

골드 V

📜문제

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

🔎접근

• 구멍을 둘러싸고 있는 부분이 없었다면 치즈를 탐색해서 찾으려했는데 구멍이 있어서 치즈가 아닌 부분을 탐색해가면서 구한다.

• 탐색을 위해 BFS 와 DFS를 고민했는데 DFS 구현이 더 쉬울것같다고 판단.

🌞풀이

#include <iostream>
#include <vector>
#define MAX 101

using namespace std;

vector<int> v;
int result[MAX][MAX];
bool visited[MAX][MAX];
bool check_cheese[MAX][MAX];

int row, col; // 행 열
int rest_cheese; // 남아 있는 치즈
int cnt; // 횟수

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void DFS(int x, int y)
{
	visited[x][y] = true;

	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue; // 좌표를 벗어난경우
		if (result[nx][ny] == 1 && check_cheese[nx][ny] == false) check_cheese[nx][ny] = true; // check될 치즈
		if (result[nx][ny] == 0 && visited[nx][ny] == false) DFS(nx, ny);
	}
}

void Remove() // 체크된 치즈를 없애는 함수
{
	v.push_back(rest_cheese); // 치즈의 개수 저장
	if (rest_cheese == 0) return;
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
		{
			visited[i][j] = 0;
			if (check_cheese[i][j] == true)
			{
				check_cheese[i][j] = false;
				result[i][j] = 0;
				rest_cheese--; // 치즈를 없애면서 개수 감소
			}
		}
	}
	cnt++;
}

int main()
{
	cin >> row >> col;
	int value = 0;
  //치즈 입력
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
		{
			cin >> value;
			result[i][j] = value;
			if(value == 1) rest_cheese++;
		}
	}

	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
		{
			if (result[i][j] == 0 && visited[i][j] == false)
			{
				DFS(i, j);
				Remove();
				if (rest_cheese == 0) // 치즈가 다 없어졌을 경우
				{
					cout << cnt << "\n";
					cout << v[v.size() - 1] << "\n";
					return 0;
				}
			}
		}
	}
}

❗주의

행 : row 열 : col 정확히 구분하기

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기