🖊️ 문제

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

---

🖊️ 풀이

DFS로 풀었다.
인접한거, 최단거리니까 BFS인데,,
내가 너무 DFS를 사랑하는 것 같다
나도 모르게 재귀로 손이 가잖니...ㅠㅠ
안좋은 습관!! 어떤 방식이 있을지 생각해보고, 코딩하는 습관이 필요할 것 같다.

1. 먼저 무지성으로 풀었던 코드

#include <iostream>
#include <memory.h>
#include <vector>
using namespace std;

int M, N;
int arr[1005][1005];
int cnt;

int result = 0;

vector<pair<int, int>> vec;

void Night()
{
	for (auto& v : vec) {
		if (arr[v.first][v.second] == 0) {
			arr[v.first][v.second] = 1;
			cnt--;
		}
	}
	vec.clear();
}

void Day(int value)
{
	if (cnt <= 0) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (arr[i][j] == 0) {
					result = -1;
					return;
				}
			}
		}
		result = value;
		return;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (arr[i][j] == 1) {
				vec.push_back(make_pair(i + 1, j));
				vec.push_back(make_pair(i - 1, j));
				vec.push_back(make_pair(i, j + 1));
				vec.push_back(make_pair(i, j - 1));
			}

			if (arr[i][j] == 0 && arr[i + 1][j] == -1 && arr[i - 1][j] == -1 && arr[i][j + 1] == -1 && arr[i][j - 1] == -1) {
				result = -1;
				return;
			}
		}
	}
	Night();
	Day(value + 1);
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> M >> N;

	memset(arr, -1, sizeof(arr));

	int n;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> n;
			arr[i][j] = n;
			if (n == 0) cnt++;
		}
	}

	Day(0);

	cout << result << endl;
}

아무래도 벡터에 꾸준히 넣어주고, 전체 벡터에 대한 루프를 돌다보니, 결과는 당연히 시간초과

그래서
2. BFS로 풀었다.
다만,, result를 구하는 과정에서 더러운 변수를ㄹ 많이 써서 고치고 싶다

#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>
using namespace std;

int M, N;
int total = 0;
int arr[1005][1005];
int result = -1;
queue<pair<int, int>> q;
int dir[2][4] = { {-1, 1, 0, 0}, {0, 0, -1, 1} };
int cnt = 0;
int temp = 0;
int curCnt = 0;

void BFS()
{
	while (!q.empty() && cnt <= total) {
		for (int i = 0; i < curCnt; i++) {
			pair<int, int> cur = q.front();
			q.pop();
			cnt++;

			for (int i = 0; i < 4; i++) {
				int nextX = cur.first + dir[0][i];
				int nextY = cur.second + dir[1][i];
				if (arr[nextX][nextY] == 0) {
					q.push(make_pair(nextX, nextY));
					arr[nextX][nextY] = 1;
					temp++;
				}
			}
		}
		result++;
		curCnt = temp;
		temp = 0;
	}
	if (cnt < total) result = -1;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> M >> N;
	total = N * M;

	memset(arr, -1, sizeof(arr));

	int n;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == -1) total--;
			else if (arr[i][j] == 1) {
				q.push(make_pair(i, j));
				curCnt++;
			}
		}
	}

	BFS();

	cout << result << endl;
}