[SWEA] 1868. 파핑파핑 지뢰찾기

문제

‘파핑 파핑 지뢰 찾기’라는 유명한 게임이 있다. 이 게임은 RXC 크기의 표를 이용하는 게임인데,

표의 각 칸에는 지뢰가 있을 수도 있고 없을 수도 있다.

표의 각 칸을 클릭했을 때, 그 칸이 지뢰가 있는 칸이라면 ‘파핑 파핑!’이라는 소리와 함께 게임은 끝난다.

지뢰가 없는 칸이라면 변이 맞닿아 있거나 꼭지점이 맞닿아 있는 최대 8칸에 대해 몇 개의 지뢰가 있는지가 0에서 8사이의 숫자로 클릭한 칸에 표시된다.

만약 이 숫자가 0이라면 근처의 8방향에 지뢰가 없다는 것이 확정된 것이기 때문에 그 8방향의 칸도 자동으로 숫자를 표시해 준다.

실제 게임에서는 어떤 위치에 지뢰가 있는지 알 수 없지만, 이 문제에서는 특별히 알 수 있다고 하자.

지뢰를 ‘*’로, 지뢰가 없는 칸을 ‘.’로, 클릭한 지뢰가 없는 칸을 ‘c’로 나타냈을 때 표가 어떻게 변화되는지 나타낸다.

세 번째 예에서는 0으로 표시 될 칸들과 이와 인접한 칸들이 한 번의 클릭에 연쇄적으로 숫자가 표시된 것을 볼 수 있다.

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

 

풀이방법

높이 우선 탐색(DFS)로 영역을 모두 찾는 문제이다.

 

예시를 들어서 풀이 방법을 보면,

 

입력이 아래와 같은 때,

case 1

case 2

지뢰에 대한 정보와 이에 따른 최소 클릭 횟수는 아래와 같다.

 

case 1

case 2

0에 인접한 8방향의 노드가 한 영역이 되고 0이 없을 때는 지뢰가 아닌 노드 하나하나가 영역이 된다.

 

또한, 영역의 개수는 최소 클릭 횟수이다. 즉, case1 은 최소 클릭 횟수가 2가 되고, case2는 8이 된다.(빨간 사각형의 개수)

 

따라서 깊이 우선 탐색을 할 때, 원소값이 0인 정점을 시작으로 인접한 8방향의 정점을 탐색한다.

 

인접한 정점 중 원소값이 0인 정점이 있다면 계속해서 탐색을 한다.

 

원소값이 0인 정점 시작으로 깊이 우선 탐색을 모두 탐색했다면, 아래와 같이 사각형을 찾은 것이다.

 

빨간색 사각형은 깊이 우선 탐색으로 찾은 사각형, 파란색 사각형은 앞으로 찾아야할 사각형이다.

case 1

case 2

이후, 원소 값이 양수이면서, 방문하지 않은 정점들을 모두 찾아 깊이 우선 탐색을 한 횟수에 더해주면 최소 클릭 횟수가 된다.

 

소스코드

package samsung;

import java.util.*;

public class s_1868 {
	static int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1};
	static int[] dy = {0, 1, 0, -1, 1, -1, -1, 1};
	static int[][] a;
	static int[][] v;
	static int n;
	
	public static void dfs(int x, int y) {
		for(int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
				if(v[nx][ny] == 0 && a[nx][ny] > 0)
					v[nx][ny] = 1;
				else if(v[nx][ny] == 0 && a[nx][ny] == 0) {
					v[nx][ny] = 1;
					dfs(nx,ny);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			char[][] map = new char[n][n];
			a = new int[n][n];
			v = new int[n][n];
			int area = 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);
				}
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(map[i][j] == '*') {
						a[i][j] = -1;
						v[i][j] = 1;
						continue;
					}
					int cnt = 0;
					for(int k = 0; k < 8; k++) {
						int nx = i + dx[k];
						int ny = j + dy[k];
						if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
							if(map[nx][ny] == '*') cnt++;
						}
					}
					a[i][j] = cnt;
				}
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0;  j < n; j++) {
					if(a[i][j] == 0 && v[i][j] == 0) {
						area++;
						v[i][j] = 1;
						dfs(i, j);
					}
				}
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(v[i][j] == 0) area++;
				}
			}
			System.out.println("#" + t + " " + area);
		}
	}
}