[2638] 치즈(C++)

치즈

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

문제 해결 과정

1. 문제를 읽고 이해하기

문제 설명을 공격적으로 읽으며 문제가 원하는 바를 완전히 이해하는 것이 중요하다.
사소한 제약 조건을 잘못 이해하면 풀 수 없는 문제들이 흔하다.

골드 4의 치즈 문제(https://www.acmicpc.net/problem/2636)의 응용버전의 문제다.

문제에서 고려해야할 요소는 다음과 같다.

- 외부와 접촉해있어야 한다.

- 2면이 닿아야 녹는다.

- 가장자리는 치즈가 없다.

2. 재정의와 추상화

어느정도의 본질만 남겨두고 축약하여 다루기 쉽게 표현해야 한다.
어떤 부분을 추상화할 지를 선택하는 작업과 문제를 재정의 하는 방법들에 대한 고찰을 해야한다.

가장자리의 `0`과 접촉한 `1`인 면이 2개 이상인 칸을 지우고, 모든 칸이 비워질 때까지 반복한 횟수를 출력한다.

3. 계획 세우기

사용할 알고리즘과 자료 구조를 선택한다.
문제를 보고 어떻게 해결해야 할지 모르겠는 경우 이 과정에서 가장 많은 고민을 하게 된다.

모든 영역을 조사해야 하므로 BFS/DFS를 사용한다.

visited 배열을 integer로 두고 count를 증가시키는 방식으로 방문한 횟수를 검사하도록 한다.

BFS에서 사용할 queue와 별개로 2면이 닿은 칸을 0으로 초기화 시켜줄 지연 queue를 둔다.

4. 계획 검증하기

구현을 시작하기 전에 계획을 검증하는 과정을 거쳐야 한다.
설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인해야 한다.

• N, M: 5 <= N, M <= 100
• 시간 제한: 1초 (1억 회 연산)
• 최악의 경우: O(100* 100 * 약 50회) -> 가능

풀이 힌트

• 간단하여 패스

코드

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
queue<pair<int, int> > melting_Q;
int visited[101][101];
int board[101][101];
int N, M;

void init_data()
{
	ios::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 >> board[i][j];
		}
	}
}

void BFS(int x, int y)
{
	queue<pair<int, int> > Q;
	Q.push({x, y});
	visited[x][y] = 1;
	while (!Q.empty())
	{
		auto cur = Q.front();
		Q.pop();
		for (int i = 0; i < 4; ++i)
		{
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue ;
			if (visited[nx][ny] >= 1) 
			{
				if (visited[nx][ny] == 1 && board[nx][ny] == 1)
				{
					visited[nx][ny] = 2;
					melting_Q.push({nx, ny});
				}
				continue ;
			}
			visited[nx][ny] = 1;
			if (board[nx][ny] == 1) continue ;
			Q.push({nx, ny});
		}
	}
}

void solve()
{
	bool is_cheese = true;
	int answer = -1;
	while (is_cheese)
	{
		is_cheese = false;
		memset(visited, 0, sizeof(visited));
		answer += 1;
		BFS(0, 0);
		while (!melting_Q.empty())
		{
			is_cheese = true;
			auto cur = melting_Q.front();
			melting_Q.pop();
			board[cur.X][cur.Y] = 0;
		}
	}
	cout << answer;
}

int main(void)
{
	init_data();
	solve();
	return (0);
}

 

오랜만에 재활문제로 BFS를 택하여 풀었다..

C++과 다시 친해지는 시간을 가졌다..ㅜㅜ

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 1}; // 이런 실수를 저지르다니..

날 도운 예외 케이스..

앞으로는 테스트 케이스를 많이 만드는 습관을 들이도록 하겠다.

9 9
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 1 1 0 1 0 1 0 0
0 1 1 1 1 1 1 0 0
0 0 1 0 1 1 0 1 0
0 1 0 1 1 0 1 0 0
0 0 1 0 1 0 1 1 0
0 1 1 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.