[백준] S5 4396번 지뢰 찾기 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

4396번: 지뢰 찾기

[문제] 

지뢰찾기는 n × n 격자 위에서 이루어진다. m개의 지뢰가 각각 서로 다른 격자 위에 숨겨져 있다. 플레이어는 격자판의 어느 지점을 건드리기를 계속한다. 지뢰가 있는 지점을 건드리면 플레이어가 진다. 지뢰가 없는 지점을 건드리면, 그곳의 상하좌우 혹은 대각선으로 인접한 8개의 칸에 지뢰가 몇 개 있는지 알려주는 0과 8 사이의 숫자가 나타난다. 완전히 플레이되지 않은 게임에서 일련의 동작이 아래에 나타나 있다.

여기서, n은 8이고, m은 10이며, 빈 칸은 숫자 0을 의미하고, 올라가 있는 칸은 아직 플레이되지 않은 위치이며, 별표 모양(*)과 닮은 그림은 지뢰를 의미한다. 맨 왼쪽의 그림은 일부만이 플레이된 게임을 나타낸다. 첫 번째 그림에서 두 번째 그림으로 오면서, 플레이어는 두 번의 이동을 시행해서, 두 번 다 안전한 곳을 골랐다. 세 번째 그림을 볼 때 플레이어는 운이 썩 좋지는 않았다. 지뢰가 있는 곳을 골라서 게임에서 졌다. 플레이어는 m개의 열리지 않은 칸을 남길 때까지 계속해서 안전한 곳을 고르면 이긴다. 그 m개의 칸은 반드시 지뢰이다.

당신이 할 일은 일부가 플레이된 게임의 정보를 읽어 해당하는 격자를 출력하는 것이다.

[입력]

첫 번째 줄에는 10보다 작거나 같은 양의 정수 n이 입력된다. 다음 n개의 줄은 지뢰의 위치를 나타낸다. 각각의 줄은 n개의 문자를 사용하여 한 행을 나타낸다. 온점(.)은 지뢰가 없는 지점이며 별표(*)는 지뢰가 있는 지점이다. 다음 n개의 줄에는 길이가 n인 문자열이 입력된다. 이미 열린 칸은 영소문자 x로, 열리지 않은 칸은 온점(.)으로 표시된다. 예제 입력은 문제 설명에서의 가운데 그림과 상응한다.

[출력]

출력은 각각의 위치가 정확하게 채워진 판을 표현해야 한다. 지뢰가 없으면서 열린 칸에는 0과 8 사이의 숫자가 있어야 한다. 지뢰가 있는 칸이 열렸다면 지뢰가 있는 모든 칸이 별표(*)로 표시되어야 한다. 다른 모든 지점은 온점(.)이어야 한다.

 

 

---

[풀이]

1. 8방 탐색을 하기 위한 델타배열을 만들어준다.

2. 각 위치를 입력받는다. (지뢰맵 : boom, 열린 맵 : map)

3. map의 i, j위치가 x 즉, 열려있으면서 *이라면 flag를 true로 만들어 준다. (지뢰 칸을 열었는지 체크)

4. 폭탄이 아니라면 8방 탐색을 해서 주변에 지뢰가 몇개 있는지 체크해준다.

5. 4번에서 구해진 지뢰의 개수를 입력해준다.

6. 모든 체크가 끝나면 flag의 true, false를 체크 후 true의 경우를 *로 다 변경해서 출력해준다.

[접근]

1. 문제를 보자마자 8방탐색을 해야겠다고 생각하였다.

2. 처음에는 배열을 3개를 만들어서 하려고 했는데 3개나 필요 없다는 것을 확인하고 2개로 줄여서 문제를 해결하였다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_S5_4396 {
	static int n;
	static char[][] boom; // 지뢰칸 입력
	static char[][] map; // 결과
	static boolean flag = false; // 지뢰칸 오픈 여부
	
	// 8방 탐색을 위한 delta배열
	static int[] dx = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
	static int[] dy = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());

		boom = new char[n][n];
		map = new char[n][n];

		// 지뢰의 위치를 받는 map
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < n; j++) {

				boom[i][j] = str.charAt(j);
			}
		}

		// 열린 곳의 위치를 받는 map
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < n; j++) {

				map[i][j] = str.charAt(j);
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 주변 지뢰의 개수
				int count = 0;
				// 열린 곳이면서
				if (map[i][j] == 'x') {
					// 폭탄이라면 >> 지뢰를 모두 열어줘야 하므로 flag를 트루로 만들어 준다.
					if (boom[i][j] == '*') {
						flag = true;
					}
					// 폭탄이 아니라면
					else {
						// 8방 탐색을 해야함
						for (int k = 0; k < dx.length; k++) {
							int x = i + dx[k];
							int y = j + dy[k];
							
							// 범위를 벗어나지 않고 폭탄이라면
							if (x >= 0 && x < n && y >= 0 && y < n && boom[x][y] == '*') {
								count++;
							}
						}
						// 해당 위치에 count를 표시해줘야 하므로
						map[i][j] = (char)(count + '0');
					}
				}
				// 열린 곳이 아니라면 .표시
				else {
					map[i][j] = '.';
				}
			}
		}
		
		// 만약 지뢰가 있는 곳을 열었다면
		if (flag) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					// 지뢰인 곳은
					if (boom[i][j] == '*') {
						// 모두 *로 변경
						map[i][j] = '*';
					}
				}
			}
		}
		
		// 출력
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
}