[SWEA 1868] 파핑파핑 지뢰찾기

이걸 DFS로 풀으려고 했던 이유를 0자 이내로 서술하시오

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
int T;
int N;
char board[300 + 2][300 + 2];
int score[300 + 2][300 + 2];	// 주변에 지뢰 몇개있는지 저장할 맵


struct _st
{
	int x, y;
};
std::vector<_st> Z;	// 주변에 지뢰가 0개인 좌표들을 담을 벡터
std::queue<_st> Q;
int visited[300 + 2][300 + 2];


int zeros;
int click;

int dir_x[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
int dir_y[8] = { 0, 1, -1, 1, -1, 0, 1, -1 };


void init()
{
	zeros = 0;
	click = 0;
	for (int i = 0; i <= 300; i++) {
		for (int j = 0; j <= 300; j++) {
			board[i][j] = '.';
		}
	}
	memset(score, -1, sizeof(score));
}

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", &board[i]);
	}
}

void make_map()
{
	// 각 좌표를 탐색하면서 근처에 지뢰가 몇 개 있는지 살핀다. 
	Z.clear();	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) { 
			if (board[i][j] == '*') continue;

			int cnt = 0;
			for (int p = 0; p < 8; p++) {
				int nx = i + dir_x[p];
				int ny = j + dir_y[p];

				if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
				if (board[nx][ny] == '*') cnt++;
			}
			score[i][j] = cnt;
			if (cnt == 0) Z.push_back({ i, j });
		}
	}
	//debug();
}

void BFS(int x, int y)
{
	Q.push({ x, y });
	visited[x][y] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 8; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (board[nx][ny] == '*') continue;
			if (visited[nx][ny]) continue;
			if (score[nx][ny] == 0) {
				Q.push({ nx, ny });
				visited[nx][ny] = 1;
				continue;
			}
			visited[nx][ny] = 1;
		}
	}
	//debugg();
}

void FF()
{
	memset(visited, 0, sizeof(visited));

	for (_st z : Z) {
		if (visited[z.x][z.y]) continue;
		zeros++;
		BFS(z.x, z.y);
	}
}


void open_cann()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == '.' && visited[i][j] == 0) click++;
		}
	}
}


int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		init();
		input();
		make_map();
		FF();
		open_cann();	// 지뢰 있는 칸이 아니면서 방문 아직 안한 칸 세어주기 
		printf("#%d %d\n", t, zeros + click);
	}
	return 0;
}

"최소 클릭수"를 구해야하므로 인접한 8방향에 지뢰가 없는 칸 부터 클릭해야 한다. 

=> 이를 위해 Flood Fill 탐색 전에 make_map 함수를 통해 각 좌표에서 인접한 지뢰의 개수를 저장해주었다. 이때 지뢰의 개수가 0인 좌표만 벡터 Z에 저장하여 Flood Fill에 사용했다.

 

"연쇄 작용"을 구현하는 방법은 알다시피 BFS이다.

score[x][y] == 0과 인접한 좌표를 탐색하는데, 만약 그 인접한 좌표의 score 배열 값도 0이면 (즉 8방향에 지뢰가 없으면) Q에 담아준다. 

이때 탐색한 좌표는 방문처리 해준다. 

 

연쇄작용을 통해 방문하지 "못한" 좌표들은 무조건 클릭 해주어야 한다. 

따라서 이 과정은 맵을 한번 스캔하여 방문하지 않은 좌표들의 개수를 구해주었다.