[C++] 삼성 1868. 파핑파핑 지뢰찾기

(2시간) 딱봐도 큐 사용해서 연쇄적으로 숫자가 표시되는 범위를 구하고 한번으로 치면 될거 같았는데 막상 구현할 때는 한참 헤맴.

 

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>

using namespace std;

int table[300][300];
bool check[300][300];
int N;
int dir[8][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };

// 주변에 지뢰가 있는지 판별
bool mineCheck(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int new_x = x + dir[i][0];
		int new_y = y + dir[i][1];

		if (new_x < 0 || new_y < 0 || new_x >= N || new_y >= N) continue;

		if (table[new_x][new_y] == 1) return false;
	}
	return true;
}

// i, j 좌표를 기준으로 연쇄적으로 숫자가 밝혀지는 부분을 전부 표시
void findMine(int i, int j) {
	queue<pair<int, int>> q;
	q.push(make_pair(i, j));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int new_x = x + dir[i][0];
			int new_y = y + dir[i][1];

			if (new_x < 0 || new_y < 0 || new_x >= N || new_y >= N) continue;

			if (!check[new_x][new_y]) {
				check[new_x][new_y] = true;
				if (mineCheck(new_x, new_y)) {
					q.push(make_pair(new_x, new_y));
				}
			}
		}
	}
}

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		memset(check, false, sizeof(check));
		memset(table, 0, sizeof(table));
		cin >> N;
		// 지뢰가 있는 경우 1로 치환
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				char tmp;
				cin >> tmp;
				if (tmp == '*') {
					table[i][j] = 1;
					check[i][j] = true;
				}
			}
		}

		int answer = 0; 
		// 주변에 지뢰가 없어 연쇄적으로 숫자가 표시되는 부분
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!check[i][j]) {
					if (mineCheck(i, j)) {
						check[i][j] = true;
						findMine(i, j);
						answer++;
					}
				}
			}
		}

		// 주변에 지뢰가 있어 따로 클릭해야 되는 부분
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!check[i][j]) {
					answer++;
				}
			}
		}

		cout << "#" << t << " " << answer << endl;
	}
	return 0;
}