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

[문제링크]

SW Expert Academy

 

0. 한번의 클릭으로 하나 이상의 칸을 처리할 수 있는건 0인 칸 뿐이다

 

1. 미리 지뢰가 아닌 칸의 개수를 세둔다 (cnt)

 

2. 주변 지뢰의 갯수로 정답 배열을 미리 만들어놓고, 0이면서 처리되지 않은 칸에 대해서만 재귀로 주변 처리

  - 한 칸 처리할때마다 cnt에서 1씩 뺀다

 

3. 모든 0에 대해 처리하고 나면, 나머지 칸들은 하나하나 직접 눌러줘야한다 (남은 cnt만큼)

 

4. 0을 누른 횟수 + 나머지를 누른 횟수 = 정답

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			N = pint(br.readLine());
			map = new int[N][N];
			ansMap = new int[N][N];
			
			int pressCnt=0;//몇번 눌러야 하는가?
			cnt=0;//지뢰가 아닌 땅 cnt
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j]=s.charAt(j);
					if(map[i][j]=='.')cnt++;
				}
			}
			//정답배열 생성
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					for (int x = Math.max(i-1, 0); x < Math.min(i+2, N) ; x++) {
						for (int y = Math.max(j-1, 0); y < Math.min(j+2, N); y++) {
							if(map[x][y]=='*')ansMap[i][j]++;
						}
					}
				}
			}
			
			//모든 0부터 눌러본다
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(ansMap[i][j]==0 && map[i][j]=='.') {
						press(i,j);
						pressCnt++;
					}
				}
			}

			sb.append("#").append(testcase).append(" ").append(pressCnt+cnt).append("\n");
			
		}System.out.println(sb);
	}
    
	static int cnt,N;
	static int[][]map;
	static int[][]ansMap;
	static int[]dx = {1,1,0,-1,-1, -1, 0, 1};
	static int[]dy = {0,1,1, 1, 0, -1,-1,-1};
    
	static void press(int x, int y) {
		if(ansMap[x][y]!=0) {
			cnt--;
			map[x][y]=ansMap[x][y];
		}
		else {
			cnt--;
			map[x][y]=0;
			for (int i = 0; i < 8; i++) {
				int tx = x+dx[i], ty=y+dy[i];
				if(tx<0||tx>=N||ty<0||ty>=N||map[tx][ty]!='.')continue;
				press(x+dx[i],y+dy[i]);
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면