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

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE&problemTitle=%ED%8C%8C%ED%95%91&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

✔ 문제 조건

1. R * C 크기 map
   • 각 칸은 지뢰 or 빈칸
2. 지뢰 클릭 시 게임 종료
3. 지뢰가 없는 칸 클릭 시 : 인접한 8방향 칸에 몇 개의 지뢰가 있는지 숫자로 표시
   • 이 숫자가 0이라면 (= 근처에 지뢰가 없다면), 근처 8방향의 칸도 자동으로 숫자 표시
4. 지뢰가 없는 모든 칸에 숫자가 표시되려면 최소 몇 번 클릭해야 하는지 출력

 

✔ 접근 과정

1. map의 시작점부터, 아직 지뢰 개수를 세지 않았는데 , 개수가 0이 될 지점에서 bfs를 시작한다.
   1. bfs를 시작할 때 마다 클릭 수 +1
   2. 현재 지점에서의 지뢰 개수를 초기화 한다.
   3. 지뢰 개수가 0이라면 큐에 넣어서 다음 탐색 대상으로 삼는다.
2. map의 끝까지 달했지만 아직 지뢰 개수를 세지 않았는 경우가 있다. 클릭 수 +1 해주며 세준다.

 

✔ 주의할 점

• 지뢰 개수가 0이 될 칸들 중, 어느 칸을 먼저 택하느냐에 따라 클릭 수가 달라질 것이라 생각했지만. 어차피 개수가 0이 되면 큐에 넣어 클릭하지 않고도 다음 탐색 대상으로 삼기 때문에 상관 없다.
• 0이 되지 않을 칸들은 어느 칸을 먼저 세든, 연쇄 작용이 일어나지 않아 무조건 클릭 수가 1씩 늘어난다.
• map 초기화 당시, 빈 칸의 개수를 세어놓아서, 빈 칸을 다 셀 때 까지 반복문을 돌리든 해야한다고 생각했는데
• 즉, 지뢰 개수가 0일 칸들을 먼저 클릭하여 세주고, 남는 칸들을 차례로 세주면 된다는 발상만 하면 쉽게 풀 수 있었다.
• map에 숫자를 기록해주기 때문에 따로 방문 배열이 필요 없을 것이라 생각했는데, 배열 체크가 없으니 14번째 테스트 케이스가 무한 루프에 빠진다. 왜지..? 아직도 이해를 못하겠음..

import java.io.*;
import java.util.*;
// 210421

public class Solution_D4_1868_파핑파핑지뢰찾기 {
	static int N, click;
	static char[][] map; // * -> 지뢰, . -> 빈칸
	static boolean[][] v;
	static int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
	static class Pos {
		int r,c;

		public Pos(int r, int c) {
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Pos [r=" + r + ", c=" + c + "]";
		}			
	}
	
	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input_D4_1868_파핑파핑지뢰찾기.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		
		int T = stoi(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			N = stoi(br.readLine());
			map = new char[N][N];
			v = new boolean[N][N];
			
			for(int i=0; i<N; i++) {
				map[i] = br.readLine().toCharArray();
			}
			
			// 빈칸들에서 시작
			click = 0;
			solve();
			
			sb.append("#" + tc + " " + click + "\n");
		} // tc

		System.out.println(sb.toString());
		br.close();
	}
	
	static void solve() {

		
		// 1. 빈 칸 중, 주위 8방의 지뢰 개수가 0이 될 칸들 먼저 세준다.
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j]!='.') continue;
				if(countMine(i, j)==0) {
					++click;
					bfs(i, j);
				}
			}
		}
		
		// 2. 세어지지 못한 칸들을 세준다.
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j]=='.') {
					++click;
					map[i][j] = (char) (countMine(i, j) + '0');
				}
			}
		}
	}
	
	static void bfs(int r, int c) {
		v[r][c] = true;
		Queue<Pos> q = new ArrayDeque<Pos>();
		q.offer(new Pos(r, c));
		
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			int mine = countMine(cur.r, cur.c);
			map[cur.r][cur.c] = (char) (mine + '0');
			
			if(mine==0) {
				// 인접한 8방향 칸들 중, 아직 개수가 세어지지 않은 칸은 탐색 대상
				for(int d=0; d<8; d++) {
					int nr = cur.r + dr[d];
					int nc = cur.c + dc[d];
					if(nr<0 || nr>=N || nc<0 || nc>=N || v[nr][nc]) continue;
					if(map[nr][nc]=='.') {						
						v[nr][nc] = true;
						q.offer(new Pos(nr, nc));
					}
				}
			}
		}
	}
	
	static int countMine(int r, int c) {
		int mine = 0;
		
		for(int d=0; d<8; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr<0 || nr>=N || nc<0 || nc>=N) continue;
			if(map[nr][nc]=='*') ++mine;
		}
		return mine;
	}
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
}