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

1. 유형

구현, bfs

 

2. 풀이

 

완전탐색을 하면서 8방향에 지뢰가 없는 칸을 찾는다.

 

찾은 칸에서도 똑같이 8방향에 지뢰가 없으면 큐에 넣고 bfs를 돌린다

 

3. 코드

현재 좌표에서 8방향을 탐색해서 지뢰가 없어야지 bfs를 돌리는게 가능하다

 

bfs를 돌릴때도 8방향에 지뢰가 없어야 다음 좌표를 탐색할 수 있다.

 

위의 과정이 다 끝난 후 아직 true로 바뀌지 않은 곳은 무조건 선택을 해야 하는 곳이다.

 

전체코드

package swea;

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

public class Swea_1868파핑파핑_지뢰찾기 {
	static class Pair{
		int r,c;
		public Pair(int r, int c) {
			this.r=r;
			this.c=c;
		}
	}
	static int dr[] = {-1,1,0,0,-1,-1,1,1};
	static int dc[] = {0,0,-1,1,-1,1,-1,1};
	static int N, ans;
	static char map[][];
	static boolean visit[][];
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int T = Integer.valueOf(st.nextToken());
		for(int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(in.readLine(), " ");
			N = Integer.valueOf(st.nextToken());
			map = new char[N][N];
			visit = new boolean[N][N];
			for(int i=0; i<N; i++) {
				String str = in.readLine();
				for(int j=0; j<N; j++) {
					map[i][j] = str.charAt(j);
					if(map[i][j]=='*') visit[i][j] = true;
				}
			}
			ans=0;
			for(int i=0; i<N;i ++) {
				for(int j=0; j<N; j++) {
					if(!visit[i][j] && map[i][j]=='.' && checkBoom(i,j)) {
						ans++;
						visit[i][j]=true;
						bfs(i,j);
					}
				}
			}
			for(int i=0; i<N;i ++) {
				for(int j=0; j<N; j++) {
					if(!visit[i][j])
						ans++;
				}
			}
			System.out.println("#"+tc+" "+ans);
		}//테스트케이스
	}
	static void bfs(int r, int c) {
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(r,c));
		while(!q.isEmpty()) {
			Pair cur = q.poll();
			if(!checkBoom(cur.r, cur.c)) continue;
			for(int i=0; i<8; i++) {
				int nr = cur.r+dr[i];
				int nc = cur.c+dc[i];
				if(nr<0 || nc<0|| nr>=N || nc>=N) continue;
				if(visit[nr][nc]) continue;
				visit[nr][nc] = true;
				q.add(new Pair(nr,nc));
			}
		}
	}
	
	static boolean checkBoom(int r, int c) {
		for(int i=0; i<8; i++) {
			int nr = r+dr[i];
			int nc = c+dc[i];
			if(nr<0 || nc<0|| nr>=N || nc>=N) continue;
			if(map[nr][nc]=='*') return false;
		}
		return true;
	}
}