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

1. 문제

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE

SW Expert Academy

 

2. 접근방법

원래 우리가 보통하던 지뢰찾기 게임 이름이 파핑파핑 지뢰찾기 였나보다.

지뢰 위치와 빈칸의 위치가 주어졌을 때

가장 적은 클릭으로 모든맵을 여는 방법을 구하는 문제이다

 

그런데 문제 조건중 클릭 시 더 많은 칸이 열리는 방법은 단 한가지 뿐이다.

 

8방이 다 0인 곳을 클릭했을때 주변이 연쇄적으로 쭉쭉 퍼져나가는 것

 

즉 그냥 8방이 0인 곳을 전부다 클릭하고 남아있는 . 의 갯수만큼

클릭 수를 추가해주면 끝나는 문제이다.

 

이제 8방이 0인곳을 펼쳤을때 연쇄적으로 펼쳐지는 것만 재귀를 이용해 짜면 해결 가능하다.

 

3. 자바 코드

package D4;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1868파핑파핑지뢰찾기 {
	
	static char map[][];
	static int mine,dot,N,click;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1 ; tc <= T ; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new char[N][N];
			mine = 0;
			dot = 0;
			click = 0;
			for(int i = 0 ; i < N ; i++) {
				map[i] = br.readLine().toCharArray();
				for(int j = 0 ; j < N ; j++) {
					if(map[i][j] == '.')
						dot++;
					else
						mine++;
				}
			}
			for(int i = 0 ; i < N ; i++) {
				for(int j = 0 ; j < N ; j++) {
					if(map[i][j] == '*')
						continue;
					if(count(i,j) == 0) {
						click++;
						spread(i,j);
					}
				}
			}
			System.out.println("#"+tc+" "+ (dot+click));
			
		}
	}
	static int dr[] = {-1,-1,0,1,1,1,0,-1};
	static int dc[] = {0,1,1,1,0,-1,-1,-1};
	
	static int count(int x, int y) {
		int mymine = 0;
		for(int i = 0 ; i < 8 ; i++) {
			int row = x+dr[i];
			int col = y+dc[i];
			if(row<0 || col<0 || row>=N || col>= N)
				continue;
			if(map[row][col] == '*')
				mymine++;
		}
		
		return mymine;
	}
	static void spread(int x , int y) {
		int cnt = count(x,y);
		dot--;
		if(cnt == 0) {
			map[x][y] = '-';
			for(int i = 0 ; i < 8 ; i++) {
				int row = x+dr[i];
				int col = y+dc[i];
				if(row<0 || col<0 || row>=N || col>= N)
					continue;
				if(map[row][col] != '.')
					continue;
				spread(row,col);
			}
		}else {
			map[x][y] = '-';
		}
		
	}
}

4. 마치며

이 문제도 결국은 연쇄적으로 0을 퍼치는게 가장 중요했던 구현문제였다.

 

지뢰찾기를 많이 해봤던 사람은 금방 파악했을지도?