[SWEA 1868] 파핑파핑 지뢰찾기 (JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc

SW Expert Academy

1. 주의할 점

- 4방향 탐색 : X, 8방향 탐색: O

- 2차 배열을 3개 사용하며 방문했는지 체크하는 Check[][], 정답 배열인 Mine[][], 입력받는 배열인 Arr[][]를 사용한다.

 

2. 구현

- 만약 입력받은 배열 Arr[][]의 값이 '*' 즉, 지뢰라면 현 위치 기준으로 8방향에 Mine배열에 1씩 더한다.

- Mine배열을 처음부터 끝까지 살피면서 Check값이 False이며 Mine값이 0인 점을 Queue에 넣고, Result++하고 8방향 BFS를 한다.

만약 8방향중 Mine값이 0인 점이 있다면 큐에 추가적으로 넣는다. 또한, 탐색한 8방향과 시작좌표는 Check값을 True로 전환한다. 

- BFS가 끝났다면 Mine배열 중 지뢰가 아니며, Check값이 False인 좌표가 있다면 Result++한다.

 

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

public class Solution_d4_1868_파핑파핑지뢰찾기 {
	static class Info {
		int x, y;
		public Info(int y, int x) {
			this.x = x;
			this.y = y;
		}
	}
	static boolean check[][];
	static char arr[][];
	static int mine[][];
	static int num, result;
	final static int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
	final static int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine().trim());
		for (int t = 1; t <= test; t++) {
			num = Integer.parseInt(br.readLine().trim());
			// 초기화
			result = 0;
			arr = new char[num][num];
			check = new boolean[num][num];
			mine = new int[num][num];
			for (int i = 0; i < num; i++)
				arr[i] = br.readLine().toCharArray();

			for (int i = 0; i < num; i++) {
				for (int j = 0; j < num; j++) {
					if (arr[i][j] == '*') {
						for (int k = 0; k < 8; k++) {
							int nx = j + dx[k];
							int ny = i + dy[k];
							if (nx >= 0 && ny >= 0 && nx < num && ny < num)
								mine[ny][nx]++;
						}
						check[i][j] = true;
					}
				}
			}
			Info ii;
			// 0인것부터 다 구하기
			for (int i = 0; i < num; i++) {
				for (int j = 0; j < num; j++) {
					if (mine[i][j] == 0 && !check[i][j]) {
						result++;
						check[i][j] = true;
						Queue<Info> q = new LinkedList<>();
						q.offer(new Info(i, j));
						while (!q.isEmpty()) {
							ii = q.poll();
							int cx = ii.x;
							int cy = ii.y;
							for (int k = 0; k < 8; k++) {
								int nx = cx + dx[k];
								int ny = cy + dy[k];
								if (nx >= 0 && ny >= 0 && nx < num && ny < num && arr[ny][nx] != '*'&& !check[ny][nx]) {
									check[ny][nx] = true;
									if (mine[ny][nx] == 0)
										q.offer(new Info(ny, nx));
								}
							}
						}
					}
				}
			}
			for (int i = 0; i < num; i++) {
				for (int j = 0; j < num; j++) {
					if (arr[i][j] != '*' && !check[i][j]) {
						check[i][j] = true;
						result++;
					}
				}
			}
			System.out.println("#"+t+" "+result);
		}
	}
}