1868. 파핑파핑 지뢰찾기

링크

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

SW Expert Academy

 

분류

그래프 탐색

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

1. 지뢰들을 대상으로 지뢰 주변을 "주변에 지뢰 있음" 상태로 바꾼다.

2. "주변에 지뢰 있음" 상태가 아니면서 "지뢰" 상태가 아닌 칸을 클릭한다. 클릭 횟수를 기록한다.

3. 모두 클릭했음에도 불구하고 남아있는 "주변에 지뢰 있음" 칸의 갯수를 세서 더한다.

 

시행착오

없음

 

코드

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

class Solution{

	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int tc = 1; tc <= T; ++tc){
			int N = Integer.parseInt(br.readLine());
			int[][] map = new int[N][N]; //0 빈공간, 2 지뢰, 1 주변에지뢰, 999 범위초과, 3 visited

			for (int i = 0; i < N; i++){
				char[] arr = br.readLine().toCharArray();
				
				for (int j = 0; j < N; j++){
					if (arr[j] == '*'){
						map[i][j] = 2;
						setMapAround(map, N, i, j, 1);
					}
				}
			}

			int cnt = 0;
			for (int i = 0; i < N; i++){
				for (int j = 0; j < N; j++){
					if (map[i][j] == 0){
						setMapVisited(map, N, i, j);
						cnt++;
					}
				}
			}


			for (int i = 0; i < N; i++){
				for (int j = 0; j < N; j++){
					if (map[i][j] == 1) cnt++;
				}
			}

			System.out.println("#" + tc + " " + cnt);
		}
	}

	public static void setMap(int[][] map, int N, int x, int y, int v){
		if (x < 0 || y < 0 || x >= N || y >= N || map[x][y] == 2) return;
		map[x][y] = v;
	}

	public static void setMapAround(int[][] map, int N, int x, int y, int v){
		int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
		int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

		for (int i = 0; i < 8; i++){
			for (int j = 0; j < 8; j++){
				setMap(map, N, x + dx[i], y + dy[j], v);
			}
		}
	}

	public static void setMapVisited(int[][] map, int N, int x, int y){
		int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1, 0};
		int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1, 0};

		for (int i = 0; i < 9; i++){
			for (int j = 0; j < 9; j++){
				int xx = x + dx[i], yy = y + dy[j];
				int m = getMap(map, N, xx, yy);
				if (m == 0){
					setMap(map, N, xx, yy, 3);
					setMapVisited(map, N, xx, yy);
				}else if (m == 1) setMap(map, N, xx, yy, 3);
			}
		}
	}

	public static int getMap(int[][] map, int N, int x, int y){
		if (x < 0 || y < 0 || x >= N || y >= N) return 999;
		return map[x][y];
	}
}