[Silver V] 지뢰 찾기

[문제 위치]

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

[문제 풀이]

 

이 문제는 지뢰의 개수가 숫자로 주어진 입력을 바탕으로, 각 빈 칸에 인접한 지뢰의 총합을 계산해 출력하는 방식이다. 일반적인 지뢰찾기와 달리, 한 칸에 여러 개의 지뢰가 들어갈 수 있기 때문에 입력에서 숫자가 적힌 칸은 단순한 지뢰 표시가 아닌, 지뢰의 개수 자체를 의미한다.

가장 먼저 해야 할 일은 입력에서 지뢰의 위치와 그 개수를 파악하는 것이다. 입력은 문자열 형태로 주어지며, 빈 칸은 '.'으로, 지뢰는 '1'부터 '9'까지의 숫자로 표현된다. 이 숫자는 해당 위치에 몇 개의 지뢰가 묻혀 있는지를 나타낸다.

다음으로는 지뢰가 아닌 칸에 대해, 인접한 여덟 방향을 확인하여 그 주변에 있는 지뢰의 개수를 합산해야 한다. 이때 주의할 점은, 인접한 칸이 맵의 범위를 벗어나지 않는지 확인하는 것이다. 각 방향마다 반복적으로 확인하면서 누적된 지뢰 수를 결과 맵에 저장한다.

최종적으로는 결과 맵을 출력하는 단계다. 지뢰가 있는 칸은 '*'로 출력하며, 지뢰가 아닌 칸에는 그 주변에 존재하는 지뢰의 총 개수를 출력한다. 이 숫자가 10 이상이 될 경우에는 'M'(Many)으로 표현하여 과도하게 많은 지뢰를 구분한다.

이 방식은 각 지뢰에서 영향을 주는 방향으로 값을 퍼뜨리는 구조로, 시간복잡도는 맵 전체를 한 번 순회하며 계산하는 수준으로 제한 시간 내에 충분히 처리 가능하다.

 

아래는 이를 구현한 코드이다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int N;
vector<string> inputMap;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
	cin >> N;
	inputMap.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> inputMap[i];
	}

	vector<vector<int>> result(N, vector<int>(N, 0));
	vector<vector<bool>> isMine(N, vector<bool>(N, false));

	// 지뢰 위치 저장
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (isdigit(inputMap[i][j])) {
				isMine[i][j] = true;
			}
		}
	}

	// 지뢰 주변 값 계산
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (isdigit(inputMap[i][j])) {
				int mineCount = inputMap[i][j] - '0';
				for (int d = 0; d < 8; ++d) {
					int ni = i + dx[d];
					int nj = j + dy[d];
					if (ni >= 0 && ni < N && nj >= 0 && nj < N && !isMine[ni][nj]) {
						result[ni][nj] += mineCount;
					}
				}
			}
		}
	}

	// 출력
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (isMine[i][j]) {
				cout << '*';
			} else if (result[i][j] >= 10) {
				cout << 'M';
			} else {
				cout << result[i][j];
			}
		}
		cout << '\n';
	}

	return 0;
}