[SWEA/C++] 파핑파핑 지뢰 찾기(1868번)

1. 문제 개요

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc 

SW Expert Academy

※ 본 문제는 SW Expert 아카데미의 문제이므로 무단으로 복제 X

1-1. 설명

우리가 생각하는 지뢰찾기 게임을 문제로 가져온다. 지뢰 찾기 맵의 크기와 맵이 주어질 때, 지뢰 칸을 제외한 다른 모든 칸의 숫자들이 표시되려면 최소 몇번의 클릭을 해야하는지 프로그램을 구현한다. 자세한 설명은 위의 문제를 참조한다. 

1-2. 제한 사항

 - 각 테스트 케이스의 첫줄에 하나의 정수 N 주어짐

 - N은 1 이상 300 이하, 이는 지뢰 찾기 표의 크기가 N * N 임을 나타냄

 - i 번째 줄에는 길이가 N인 문자열 주어짐

 - * 이면 지뢰이고, . 이면 지뢰가 없다는 뜻

---

2. 구현

2-1. 풀이

그래프를 이용하는 문제임을 인지하고, BFS로 풀어야겠다고 생각하여 BFS를 구현해주었다. 또한 8방향에 지뢰가 있는지 없는지 판단을 해야하므로, checkBomb 함수를 생성하여 각 맵마다 체크해주었다. 여기서 방문 맵을 생성할 때, 지뢰일 경우 방문했다고 표시를 해주어야 한다. 또 주의해야 할 점은 4방향이 아닌, 대각선까지 포함한 8방향을 확인해야 한다는 것이다. 그렇게 어려운 문제는 아니었지만, 그래프에 대한 문제를 자주 풀어보지 않아 살짝 헤맸다. 

2-2. 코드

#include<iostream>
#include <cstring>
using namespace std;

struct Node {
	int x, y;
};

char map[300][300];
bool visited[300][300];
Node queue[90000];
int N;

int dirX[8] = { 1, -1, 0, 0, 1,1, -1, -1 };
int dirY[8] = { 0, 0, -1, 1, -1, 1, -1, 1 };

bool checkBomb(int x, int y);
void BFS(int x, int y);

int main(int argc, char** argv)
{
	int T, result = 0;;
	char input;
	cin >> T;
	for (int test_case = 1; test_case <= T; ++test_case) {
		cin >> N;
		memset(map, '.', sizeof(map));
		memset(visited, false, sizeof(map));

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> input;
				map[i][j] = input; // 지뢰 판 저장
				if (input == '*') visited[i][j] = true; // 지뢰일 때 방문 노드 표시
			}
		}

		result = 0; // 결과값
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (checkBomb(i, j) && !visited[i][j]) { // 8방향 지뢰가 없으며, 방문하지 않았을 때
					BFS(i, j); // BFS를 통해 주변 노드 방문
					result++; // 결과값 +1
				}
			}
		}

		// 방문하지 못한 단일 노드 존재 시 표시
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) result++;
			}
		}
		cout << '#' << test_case << ' ' << result << "\n";
	}
	return 0;
}

bool checkBomb(int x, int y) { // 8 방향 지뢰 유, 무
	for (int i = 0; i < 8; i++) {
		int nextX = x + dirX[i];
		int nextY = y + dirY[i];

		if ((nextX >= 0) && (nextX < N) && (nextY >= 0) && (nextY < N)) {
			if (map[nextX][nextY] == '*') return false; // 지뢰 존재 시
		}
	}
	return true; // 지뢰 미존재 시
}

void BFS(int x, int y) {
	int startX = x, startY = y;
	int front = -1, rear = -1;
	queue[++rear] = { startX, startY }; // x, y가 저장된 queue
	visited[startX][startY] = true;

	while (front != rear) {
		Node num = queue[++front];

		for (int i = 0; i < 8; i++) { // 8 방향
			int nextX = num.x + dirX[i];
			int nextY = num.y + dirY[i];

			if ((nextX >= 0) && (nextX < N) && (nextY >= 0) && (nextY < N)) { // 범위 안에 존재 시
				if (visited[nextX][nextY]) continue; // 이미 방문한 노드일 때 continue
				visited[nextX][nextY] = true; // 방문 했음을 표시
				if (checkBomb(nextX, nextY)) { // 8 방향으로 지뢰가 존재하지 않을 때
					queue[++rear] = { nextX, nextY }; // queue에 저장
				}
			}
		}
	}
}