SWEA 1868 - 파핑파핑 지뢰찾기

Java

1868 번 - 파핑파핑 지뢰찾기

문제

파핑 파핑 지뢰 찾기를 할 때 표의 크기와 표가 주어질 때, 지뢰가 있는 칸을 제외한 다른 모든 칸의 숫자들이 표시되려면 최소 몇 번의 클릭을 해야 하는지 구하는 프로그램을 작성하라.

접근 방법

코드

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

class Solution {
	static int result = 0, n, blankCnt;
	static char[][] board;
	static int[][] mine;
	static List<int[]> chkSpot;
	public static void main(String []args) throws Exception {  
		System.setIn(new FileInputStream("res/input.txt"));	//제출 할 때 주석해야함
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		result = 0;
    		n = stoi(br.readLine());
    		board = new char[n][n];
    		mine = new int[n][n];
    		String str;
    		for(int i = 0; i < n; i++) {
    			str = br.readLine();
    			for(int j = 0; j < n; j++) {
    				board[i][j] = str.charAt(j);
    				if(board[i][j] == '.')
    					blankCnt++;
    			}
    		}
    		// --------- 초기화 끝 ---------
    		chkSpot = new ArrayList<>();
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(board[i][j] == '*')
    					mine[i][j] = -1;
    				else
    					mine[i][j] = CntMine(i,j);
    				
    				if(mine[i][j] == 0)
    					chkSpot.add(new int[] {i, j});
    			}
    		}
    		
    		for(int[] curP : chkSpot) {
    			Click(curP[0], curP[1]);
    		}
    		    		
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(board[i][j] == '.')
    					result++;
    			}
    		} 
    		System.out.println("#" + tidx + " " + result);
    	}
    	
	}

	// 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
    static int dy[] = {-1,1,0,0,-1,-1,1,1};
	static int dx[] = {0,0,-1,1,-1,1,-1,1};
	
	// 사방에 지뢰가 있는지 없는지 확인하는 함수
	public static boolean isNear(int y, int x) {
		int ny,nx;
		for(int i = 0; i < 8; i++) {
			ny = y + dy[i];
			nx = x + dx[i];
			
			if(isIn(ny,nx) && board[ny][nx] == '*')
				return true;
		}
		return false;
	}
	
	// 사방 지뢰 개수를 센다.
	public static int CntMine(int y, int x) {
		int ny,nx, cnt = 0;
		for(int i = 0; i < 8; i++) {
			ny = y + dy[i];
			nx = x + dx[i];
			
			if(isIn(ny,nx) && board[ny][nx] == '*')
				cnt++;
		}
		return cnt;
	}
	
	private static void Click(int y, int x) {
		if(board[y][x] == 'x') {
			return;
		}
		result++;
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {y,x});
		board[y][x] = 'x';
		
		int[] q;
		int ny,nx;
		while(!queue.isEmpty()) {
			q = queue.poll();
			y = q[0];
			x = q[1];
			
			for(int i = 0; i < 8; i++) {
				ny = y + dy[i];
				nx = x + dx[i];
				
				if(isIn(ny,nx) && board[ny][nx] == '.') {
					board[ny][nx] = 'x';
					if(!isNear(ny,nx))
						queue.add(new int[] {ny,nx});
				}
			}
		}
	}
		
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= n)
            return false;
        return true;
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점