[swexpert] 1868. 파핑파핑 지뢰찾기 (java)

1. 먼저 numbering함수에서 폭탄이 아닌 곳의 숫자를 쓴다. (for문으로 사방돌며 폭탄 몇개인지 체크, bfs필요없음)

 

2. 0인 곳의 처리 (bfs)

0인 곳은 연속으로 터지므로 큐에 0을 넣고 돌려 폭탄이 아닌 곳을 모두 폭탄(-1)로 바꿔준다. -1로 바꿔주는 것은 방문표시임과 동시에 더이상 터트릴 필요가 없어지는 숫자라고 생각하면 된다.

0의 개수만큼 cnt를 1증가시켜준다.

 

3. 1이상 숫자인 곳의 처리

마지막 배열 이중 포문을 돌면서 1이상의 숫자들은 일일히 눌러줘야하므로 만날때마다 cnt를 1증가시켜준다. 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	int y,x;

	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class Solution {
	static int t,n;
	static char[][] map;
	static int[] xpos= {-1,0,1,1,1,0,-1,-1};
	static int[] ypos= {-1,-1,-1,0,1,1,1,0};
	static int[][] num;
	static int cnt;
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			map=new char[n][n];
			num=new int[n][n];
			cnt=0;
			for (int i = 0; i < n; i++) {
				String s=sc.next();
				for (int j = 0; j < n; j++) {
					map[i][j]=s.charAt(j);
					if(map[i][j]=='*') {
						num[i][j]=-1;
					}
				}
			}
			
			numbering();
			counting();
			System.out.printf("#%d %d\n",tc,cnt);
		}
	}

	private static void counting() {
		
		//0먼저 처리
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(num[i][j]==0) {
					Queue<Pos> q=new LinkedList<Pos>();
					q.add(new Pos(i,j));
					num[i][j]=-1;
					cnt+=1;
					while(q.size()>0) {
						Pos cur=q.poll();
						int y=cur.y;
						int x=cur.x;
						for (int k = 0; k < 8; k++) {
							int yy=y+ypos[k];
							int xx=x+xpos[k];
							if(yy<0 || xx<0 || yy>=n || xx>=n)continue;
							if(num[yy][xx]>0) {
								num[yy][xx]=-1;
							}else if(num[yy][xx]==0) {
								q.add(new Pos(yy,xx));///0은 연쇄적으로 터짐
								num[yy][xx]=-1;
							}
						}
					}
				}
			}
		}
		
		//나머지 숫자 처리 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(num[i][j]>0) {
					num[i][j]=-1;
					cnt+=1;
				}
			}
		}
		
	}

	private static void numbering() {
		//숫자 표시
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(num[i][j]!=-1) {//*이 아니면
					int bomb=0;
					for (int k = 0; k < 8; k++) {
						int yy=i+ypos[k];
						int xx=j+xpos[k];
						if(yy<0 || xx<0 || yy>=n || xx>=n)continue;
						if(map[yy][xx]=='*')bomb+=1;
					}
					num[i][j]=bomb;
				}
			}
		}
		
	}
	
	
	
}