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

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

문제

---

dfs 문제이다. 지뢰 찾기에서 0을 찾고 이어지는 모든 영역을 표시한 다음 남는 영역을 카운팅해주면 된다.

포인트

---

1. 동서남북 방향을 정할 때는 dx, dy 를 설정해둔다.
2. dfs 를 시작할 때도 자신의 위치를 표시한다.

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static StringBuilder result = new StringBuilder();
	static char[][] mat;
	static int[][] cntMine;
	static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}, dy = {0, 1, 1, 1, 0, -1, -1, -1}; //12시부터 시계방향

	static int n;

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;


		int T = Integer.parseInt(br.readLine());

		///////////////////////////
		int cnt;
		///////////////////////////
		for (int test_case = 1; test_case <= T; test_case++) {
			result.append("#" + test_case + " ");

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

			//matrix 정의 후 입력, cntMine 초기화.. 사용하지 않은 부분과 실제 주변의 지뢰가 0개인 것을 구별하기 위해 -1 로 초기화
			mat = new char[n][n];
			cntMine = new int[n][n];
			cnt = 0;
			for (int i = 0; i < n; i++) {
				mat[i] = br.readLine().toCharArray();
				for (int j = 0; j < n; j++) {
					cntMine[i][j] = -1;
				}
			}

			count_mine(); //각 위치에서 지뢰의 개수를 파악한다

			//count가 0 인 부분에 대해서 dfs
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (cntMine[i][j] == 0) {
						find_mine(i, j);
						cnt++; // 0 을 한 번 누르면 주변이 모두 표시되기 되기에 큰 맥락에서 dfs 의 횟수를 센다.
					}
				}
			}

			//나머지 클릭을 위해 남은 부분 카운팅
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (mat[i][j] == '.') {
						cnt++;
					}
				}
			}

			result.append(cnt + "\n");
			System.out.print(result);
			result.setLength(0);
		}
	}


	private static void find_mine(int i, int j) {
		//클릭한 부분은 @ 로 표시
		mat[i][j] = '@';
		for (int k = 0; k < 8; k++) {
			int x = i + dx[k];
			int y = j + dy[k];
			if (x < 0 || x >= n || y < 0 || y >= n || mat[x][y] != '.') { //영역을 넘어가거나 .이 아니라면 패스 (지뢰와 이미 선택된 부분은 패스)
				continue;
			}
			if (cntMine[x][y] == 0) {
				cntMine[x][y] = -1;
				find_mine(x, y);
			} else {
				mat[x][y] = '@';
			}
		}
	}

	private static void count_mine() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (mat[i][j] == '.') {
					int cnt = 0;
					for (int k = 0; k < 8; k++) {
						int x = i + dx[k];
						int y = j + dy[k];
						if (x < 0 || x >= n || y < 0 || y >= n || mat[x][y] != '*') { //영역을 넘어가거나 지뢰가 아니라면 패스.. 지뢰만 카운팅하기 위해서 .은 패스
							continue;
						}
						cnt++;
					}
					cntMine[i][j] = cnt;
				}
			}
		}
	}

}