[Java/BFS] 1868. 파핑파핑 지뢰찾기

 

문제 링크

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc

SW Expert Academy

 

 

 

아이디어

1. map 배열의 전체를 돌면서 8방탐색을 한다. → 8방에 지뢰가 몇개 있는지 체크해서 mark 배열에 저장한다.

2. mark가 0이고(주변에 지뢰가 없고) && 클릭한 적 없고 (visited가 false) && 지뢰가 아닌 곳(map이 0)인 곳 CLICK

3. 2에서 아직 클릭 안한 곳 && 지뢰가 아닌 곳 CLICK

 

왜인지 시행착오가 좀 많았다..

0인 곳을 누르면 주변의 0인 곳과 그 테두리까지 함께 눌리게 되는데 이걸 어떻게 구현할지 고민 많이 했다.

BFS를 이용해서 0인곳은 큐에 넣어주고, 팔방탐색을 해서 지뢰가 아니기만 하면 클릭한 것으로(visited를 true) 해주면 된다.

 

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

public class Solution {

	static char[][] map;
	static int[][] mark;
	static boolean[][] visited;
	static int N;

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

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

		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());

			map = new char[N][N];
			mark = new int[N][N];
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				String line = br.readLine();
				Arrays.fill(mark[i], -1);
				for (int j = 0; j < N; j++) {
					map[i][j] = line.charAt(j);
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (mark[i][j] == -1 && map[i][j] == '.') {
						countMine();
					}
				}
			}

			int answer = 0;
			
			// 지뢰가 없는 곳부터 누르기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(mark[i][j]==0 && !visited[i][j] && map[i][j]=='.') {
						click(i,j);
						++answer;
					}
				}
			}

			
			// 눌리지 않은 곳 누르기
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(mark[i][j] > 0 && !visited[i][j] && map[i][j]=='.')
						++answer;
				}
			}
			
			System.out.println("#"+t+" "+answer);
		}

		br.close();
	}

	private static void click(int y, int x) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.offer(new int[] {y, x});
		visited[y][x] = true;
		
		while(!queue.isEmpty()) {
			int[] n = queue.poll();
			
			for(int d=0; d<8; d++) {
				int ty = n[0] + dy[d];
				int tx = n[1] + dx[d];
				
				if(ty<0 || tx<0 || ty>=N || tx>=N || visited[ty][tx] || map[ty][tx]=='*')
					continue;
				
				visited[ty][tx] = true;
				if(mark[ty][tx]==0)
					queue.offer(new int[] {ty,tx});
			}
		}
		
	}

	static int[] dy = { -1, 1, 0, 0, -1, -1, 1, 1 };
	static int[] dx = { 0, 0, -1, 1, -1, 1, -1, 1 };

	private static void countMine() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j]=='.') {
					int cnt = 0;
					for(int d=0; d<8; d++) {
						int ty = i + dy[d];
						int tx = j + dx[d];
						
						if(ty<0 || tx<0 || ty>=N || tx>=N || map[ty][tx]=='.')
							continue;
						
						++cnt;
					}
					mark[i][j] = cnt;
				}
			}
		}
	}

	private static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(mark[i][j] + " ");
			}
			System.out.println();
		}
	}

}