1868. 파핑파핑 지뢰찾기

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE

SW Expert Academy

 

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

// TODO: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE
public class Solution_BSF {

	private static int T, N;
	private static char[][] map;
	private static int[][] visited;
	private static Queue<int[]> queue;
	private static int[][] D = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new StringReader(src));
		T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= T; t++) {
			int answer = 0;
			N = Integer.parseInt(br.readLine());
			map = new char[N][N];
			visited = new int[N][N];

			for (int row = 0; row < N; row++) {
				map[row] = br.readLine().toCharArray();
			}
			for (int row = 0; row < N; row++) {
				for (int col = 0; col < N; col++) {
					// 미방문 지점 중 안전하고 땅이면 그 점을 기점으로 BFS
					if (map[row][col] == '.' && visited[row][col] == 0 && isSafeArea(row, col)) {
						bfs(row, col);
						answer++;		// 한점 콕 찔렀으므로 +1
					}
				}
			}
			// 땅 중 미방문 지점 추가로 세어주기
			for (int row = 0; row < N; row++) {
				for (int col = 0; col < N; col++) {
					if (map[row][col] == '.' && visited[row][col] == 0) {
						answer++;
					}
				}
			}
			sb.append(String.format("#%d %d\n", t, answer));
		}
		System.out.println(sb);
	}

	static void bfs(int row, int col) {
		queue = new LinkedList<>();
		// 초기 데이터 설정
		queue.add(new int[] { row, col });
		visited[row][col] = 1;

		while (!queue.isEmpty()) {
			int[] head = queue.poll();

			if (isSafeArea(head[0], head[1])) {	// 현재 지점이 안전 지대라면 주변 요소들을 까볼 수 있다.
				for (int d = 0; d < D.length; d++) {
					int nRow = head[0] + D[d][0];
					int nCol = head[1] + D[d][1];
					// 범위 내에 있고 주변에 폭탄 없고 미방문이면
					if (inRange(nRow, nCol) && map[nRow][nCol] == '.' && visited[nRow][nCol] == 0) {
						visited[nRow][nCol] = 1;
						queue.add(new int[] { nRow, nCol });
					}
				}
			}
		}
	}

	// 주변 8방향을 봐서 map 안의 영역이라면 모두 '.'인지 여부 리턴
	static boolean isSafeArea(int row, int col) {
		for (int d = 0; d < D.length; d++) {
			int nRow = row + D[d][0];
			int nCol = col + D[d][1];
			if (inRange(nRow, nCol) && map[nRow][nCol] == '*') {// 지점 안에 있는데 하나라도 지뢰가 있다면 safe 하지 않음
				return false;
			}
		}
		return true;
	}

	static boolean inRange(int row, int col) {
		return 0 <= row && 0 <= col && row < N && col < N;
	}

	// 정답: 1990
	private static String src = "1\r\n" +
			"60\r\n" +
			".......*...*.*...***..**....*.......*..*..*..*...*.**.*.**..\r\n" +
			".*....***.**...*.......*..**.*.........**..*.**..*......*.**\r\n" +
			"........*.*.*...*****.....*..*.*....*.*.*.**.**..*......*..*\r\n" +
			"**.*.**.****..*...*.....*...*.......**....*..........***.*.*\r\n" +
			".......*.**..*.***......*.***..*.***.*.***.....**..*.**.**..\r\n" +
			"*....*......*..*..**.......**........*..*.*.....*.**.**.*...\r\n" +
			"*.....*....**.*...*.....***..*.....***.**....*...*......***.\r\n" +
			"..*...*..*.*.*.******......*..*.*..*..*.*.........*...**.**.\r\n" +
			"*..*.*..*.*...***..*....*.*..**...*........*.......*.*...*..\r\n" +
			"*.****..*......*..**.*.****.....*..*.....**...**.*..*..**..*\r\n" +
			"......**..*.....*...*..*.*....*.*.....*..*..............*..*\r\n" +
			".*..**.*..*..******.*****.*...*.*.*..*....*..**.*..*...*....\r\n" +
			"**..*....*............*......*.***..*.**..**....*...*.......\r\n" +
			"..*.*.....*...*.*...**....*...**.**.*.*..**...*.......**....\r\n" +
			"......*..*.*****..**..*...*....*...*.**......***..*...**.*.*\r\n" +
			"**...*.*....*.......**.*.*.*..***..*.*..........*..*.**.*...\r\n" +
			"....*...*....*....*.*.....*.*...*.*...***..*...*..*...*..**.\r\n" +
			"...*.....*.....**.....*...*.............**..*.*.*..*......*.\r\n" +
			"*..*................*..*.*.*.**.*...*...*..*.*.*....*.**..**\r\n" +
			".*..*.*......*.**.*..*....***.......**.**.***...*..*.....*..\r\n" +
			"..*........*..*.***........***...**.*..**..****..**..*.**.*.\r\n" +
			"...*...*..*.***....*.*.....**....*.*.*.*.*..........*.....**\r\n" +
			"*.*........*...**..*.*...*............*..*.....*..*......*..\r\n" +
			"*........*..**.**..**.**...**..*...*.....*.*..*.........**.*\r\n" +
			"...*.**....*.*.........*...*....*....*..*.*.....*....**.....\r\n" +
			"....**...*...*.***..*...**....**.*..*......*.....***....*.**\r\n" +
			"**.*.*...*.*...**..**...*.**..*.*..*...*.*...*.*.......*....\r\n" +
			"...**...*..*....*.***..*.**.*......*.*.*.......*.**.*..*.*..\r\n" +
			"....*.*.*.***....*.***..**....*.....*.....*.***...*..*....*.\r\n" +
			"*..........*...*.........*.*........**...*..**......*...*..*\r\n" +
			"*.*.**..*.....****...*.........*.*.*..**..***.*...*.*..*....\r\n" +
			".....*.**..*.*....*.**....*.*....**.*.*...**.*....*.*.***.*.\r\n" +
			".....*.......**.**.**.****...**.*.....*.*..*..**.*.........*\r\n" +
			"*.****.*.*.....*...*..*.*..*...*.**.**.****..*.....*....*..*\r\n" +
			"**....**..*.....*.*...**..**.....*..****.***......***.***...\r\n" +
			"**.....***..*......*.**....***..*.*..**.**..**.....*.**.**.*\r\n" +
			".*..*....*....*..****..*.*..*..*....**......*..*...**..*..**\r\n" +
			".*........*.......*..****.*....*......................*.*.**\r\n" +
			"*.*....*.***...**....**..**.......*..*....***.*..*......**..\r\n" +
			"...*.....**..**.****.....*...*.*................*.*....***..\r\n" +
			"*.**..........*.**...**..*.***..*.*..*.....**.....*.*.....**\r\n" +
			".*....**...**..**.*..*....*...*...*..*..*.**..*.*....**.....\r\n" +
			".***............*..*....**..*****....*.......*.*....***....*\r\n" +
			".*..*.*...*..*..*..*.*.*...*.*....*.**......***.*.*...**...*\r\n" +
			"*.*...**....*..**..*.*..*...*.....**....**...*.......**..*..\r\n" +
			"*.*.***..*.*..**...*....***....*.*.*..*.**.*.*.*..**.*.***..\r\n" +
			".........*.*..*****.**.....*.*.*.*....*..*..*......**.*...*.\r\n" +
			"*..**.***........*****...*..**..*..*..*..**...**.....*.*..**\r\n" +
			"*.....*.*...........**.*..*.*.........**..***.**............\r\n" +
			"...........***..*..***...**..**.*.*..**.*.**..*.*..*....*...\r\n" +
			"*...**.....*..***...*.**.*.....*.....*......*.........*.*.*.\r\n" +
			"..**..*.*...*.**.......*****....*.*..*....**....**..*.*...**\r\n" +
			"..*...*.**.**.....*.*.**.......*...*...*....*.*..**.*.*.*...\r\n" +
			"*....*.*......*....**.*....*****.**.**....*.......**..*.....\r\n" +
			"..*.***....*......*..*..*......****....*.*.*..**..*...*....*\r\n" +
			".*.*.....*.....*.*.*...*.*....**..**.*....**...*....***.*...\r\n" +
			".......****...**.*...*.*.*.......*..**.*...*...*.....*.....*\r\n" +
			"....*.*..*.*.*...*.*..**..*.....*.***......**..*.*.*.*.*..*.\r\n" +
			"....*.....*.*..**.....*..*.*..*..*..........*..*...*...*....\r\n" +
			"**.*****.......***..*......*.*.*..............*.........**..";
}