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

접근 방법

0인 곳을 먼저 클릭해야 한다.

지뢰찾기 게임을 알고 있다면 문제 이해가 쉬워진다.

주어진 예제의 그림을 보면, C를 한번 클릭하면 오른쪽 결과가 나온다.

즉, 주변 지뢰의 수가 0이라면 연속적으로 눌리고, 지뢰의 숫자가 1 이상이면 그 자리에서 멈춘다.

bfs 방식으로 풀이했다.

 

동작 순서

(1) 맵을 설정한다. 지뢰의 수를 저장할 map 배열과, 방문 체크를 위한 v 배열을 생성한다.

지뢰(*)라면 map에는 -1을, v에는 방문 표시로 1을 체크한다.

(2) 맵에 지뢰의 수를 표시한다. 지뢰가 없는 0인 곳을 클릭하여 8방 탐색 후 지뢰의 개수를 갱신한다.

(3) 0인 곳을 먼저 누른다. 주변에 지뢰가 없는 곳이어야 하고, 방문하지 않은 곳이어야 한다.

(3-1) bfs로 8방 탐색을 한다. 0이면 큐에 넣어주고 나머지 1 이상의 숫자에 대해서는 방문처리만 해준다.

(4) 방문하지 않은 나머지를 눌러준다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Solution_1868_파핑파핑지뢰찾기 {

	static int N, res;
	static int[][] map;
	static int[][] v;

	static int[] dr = { -1, 1, 0, 0, -1, -1, 1, 1 };
	static int[] dc = { 0, 0, -1, 1, -1, 1, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N]; // 지뢰와 지뢰 수 표시 맵
			v = new int[N][N]; // 클릭한거 체크용
			res = 0;

			String str;
			for (int i = 0; i < N; i++) {
				str = br.readLine();
				for (int j = 0; j < N; j++) {
					if (str.charAt(j) == '*') {
						map[i][j] = -1; // 지뢰면 -1로 표시
						v[i][j] = 1; // 지뢰 있는 곳 방문처리
					}
				}
			} // end input

			// 맵에 지뢰 수 표시. 지뢰:-1 나머지:지뢰수
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 0) {
						// i,j위치에서 8방 지뢰 수 세기
						int cnt = 0;
						for (int d = 0; d < 8; d++) {
							int nx = i + dr[d];
							int ny = j + dc[d];

							if (!isRange(nx, ny))
								continue;
							if (map[nx][ny] != -1)
								continue;
							cnt++;
						}
						map[i][j] = cnt; // 지뢰 수 맵에 갱신
					}
				}
			}

			// 8방이 0인 곳만 누르기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 0 && v[i][j] == 0) { // 주변에 지뢰가 없고, 방문 x
						click(i, j);
						res++; // 클릭
					}
				}
			}

			// 남은 0인 부분 누르기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (v[i][j] == 0) {
						res++;
					}
				}
			}
			sb.append("#").append(tc).append(" ").append(res).append("\n");
		} // end test case
		System.out.println(sb);
	}

	private static void click(int x, int y) {
		// 8방 탐색 해서 0이라면 큐에, 지뢰가 아니고 숫자라면 방문체크만
		Queue<int[]> q = new ArrayDeque<>();
		q.offer(new int[] { x, y });
		v[x][y] = 1;// 방문체크

		while (!q.isEmpty()) {
			int[] cur = q.poll();

			for (int d = 0; d < 8; d++) {
				int nx = cur[0] + dr[d];
				int ny = cur[1] + dc[d];

				// 범위확인
				if (!isRange(nx, ny))
					continue;
				// 지뢰라면 건너뜀
				if (map[nx][ny] == -1)
					continue;
				// 이미 클릭했다면 건너뜀
				if (v[nx][ny] == 1)
					continue;
				// 0이라면 큐에 넣음
				if (map[nx][ny] == 0) {
					q.offer(new int[] { nx, ny });
				}
				// 지뢰수가 표시된 위치 방문처리
				v[nx][ny] = 1;
			}
		}
	}

	private static boolean isRange(int nx, int ny) {
		if (nx >= 0 && ny >= 0 && nx < N && ny < N)
			return true;
		return false;
	}

}

즐겨하는 게임이 지뢰찾기이면서도 0이 연속적으로 눌리는 경우에 대해서 이해하지 못했다.

지뢰찾기 왜 했지?