파핑파핑 지뢰찾기 [SWEA 1868][JAVA][D4]

[광고 누르면 오늘의 행운 상승!!]

dfs, bfs 둘 다로도 풀 수있는 문제

DFS로 풀었다.

1. 배열을 탐색하면서 탐색할 수 있는 구간이면 DFS시작

2. 8방향 탐색 후 지뢰가 있는지 검사 후 DFS

3. 8방향으로 DFS를 뻗어나가면서 맵을 갱신한다.

4. 총 횟수 출력

package Study0316;

import java.io.*;
import java.util.*;

public class 파핑파핑지뢰찾기 {
	static int[] dx = {-1,-1,0,1,1,1,0,-1};
	static int[] dy = {0,1,1,1,0,-1,-1,-1};
	static int N;
	static char[][] map;
	static boolean[][] visit;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new char[N][N];
			visit = new boolean[N][N];
			
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = s.charAt(j);
				}
			}
			int ans = 0;
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(map[i][j] != '.') continue;
					if(count(i,j) == 0) {
						ans++;
						dfs(i,j);
					}
				}
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(map[i][j] == '.') ans++;
				}
			}
			
			System.out.println("#" + tc + " " + ans);
		}
		br.close();
	
	}

	private static void dfs(int row, int col) {
		visit[row][col] = true;
		int mine = count(row,col);
		map[row][col] = (char)(mine + '0');
		
		if(map[row][col] != '0') return;
		
		for (int d = 0; d < 8; d++) {
			int nx = row + dx[d];
			int ny = col + dy[d];
			
			if(0<=nx && nx <N && 0<= ny &&ny<N 
					&& map[nx][ny] == '.' && !visit[nx][ny]) dfs(nx,ny);
		}
	}

	private static int count(int row, int col) {
		int mine = 0;
		
		for (int d = 0; d < 8; d++) {	
			int nx = row + dx[d];
			int ny = col + dy[d];
			
			if(0<=nx && nx <N && 0<= ny &&ny<N 
					&& map[nx][ny] == '*') mine++;
		}
		return mine;
	}

}