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

문제

• SWEA 1868
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

부끄럽지만 문제를 이해하는데 꽤 오랜 시간이 걸렸던 문제이다.
이 문제는 크게 2단계로 접근해볼 수 있다.

1. 2중 for문을 돌면서 지뢰가 아닌 부분을 8방향 탐색해서 숫자를 적어준다.
   1-1. 숫자가 0이면 이 좌표를 zeros리스트에 넣어준다. (생각해보니 큐나 스택에 넣어도 상관없을듯)
2. zeros리스트에서 숫자를 하나씩 꺼내서 click()함수를 호출할때마다 Ans를 1증가시킨다. click()함수에서는 8방향 탐색을 하면서 방문 처리를 하고 주변에 0이 있는 경우 이 주변을 다시 탐색하기 위해 click()함수를 호출한다. 이 경우는 첫번째 클릭으로 인해 연쇄적으로 작용되므로 Ans를 증가시킬 필요 없다.
3. 숫자가 0인 부분을 모두 체크하였다면, 이제 모든 배열을 돌면서 아직 방문하지 않은 곳을 발견하면 Ans를 1증가시킨다.
   
   이 문제의 핵심은 0을 먼저 선택함으로써 최소 선택 횟수를 줄이는 것이였다.
   나는 이런 유형과 같은 게임 문제(ex.스도쿠, 2048)에 약한것 같다… 더 연습이 필요할 것 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Solution {
	
	static int N; //크기
	static int T; //테스트케이스 수
	static int R, C;
	static int[][] map;
	static boolean[][] visited; //이미 방문했는지
	static int[] di = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dj = {-1, 0, 1, -1, 1, -1, 0, 1};
	static ArrayList<Point> zeros;
	static int Ans;
	
	public static class Point{
		int i;
		int j;
		
		public Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			visited = new boolean[N][N];
			zeros = new ArrayList<>();
			Ans = 0;
			
			for(int i=0; i<N; i++) {
				String s = br.readLine();
				for(int j=0; j<N; j++) {
					char input = s.charAt(j);
					if(input == '*') map[i][j] = -2; //지뢰
					if(input == '.') map[i][j] = -1; //지뢰아님
				}
			}//input
			
			//1. 숫자 채우기
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] == -2) continue;
					boolean isFind = false; //지뢰 찾았는지
					int findCnt = 0; //찾은 지뢰 개수
					//주변 8방향을 찾아서 숫자를 적어준다.
					for(int d=0; d<8; d++) {
						int ni = i + di[d];
						int nj = j + dj[d];
						
						//범위 안에 있는지
						if(ni>=0 && ni<N && nj>=0 && nj<N) {
							if(map[ni][nj] == -2) {
								isFind = true;
								findCnt++; //찾은 지뢰 개수 증가
							}
						}
					}
					if(!isFind) {
						map[i][j] = 0;
						zeros.add(new Point(i, j));
					}
					else map[i][j] = findCnt;
				}
			}
			
			//2. 0먼저 클릭
			for(int i=0; i<zeros.size(); i++) {
				Point p = zeros.get(i); //하나 꺼내서
				if(visited[p.i][p.j]) continue; //이미 방문했으면 다음
				visited[p.i][p.j] = true;
				click(p.i, p.j); //클릭하삼
				Ans++;
			}
			
			//3. 나머지 클릭
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] != -2 && !visited[i][j]) {
						Ans++;
					}
				}
			}
			System.out.println("#"+tc+" "+Ans);
		}
	}

	private static void click(int i, int j) {
		for(int d=0; d<8; d++) {
			int ni = i + di[d]; //다음 방향
			int nj = j + dj[d];
			
			if(ni>=0 && ni<N && nj>=0 && nj<N && !visited[ni][nj] && map[ni][nj] != -2) {
				visited[ni][nj] = true;
				if(map[ni][nj] == 0) {
					click(ni, nj);
				}
			}
		}
	}
}