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

SW Expert Academy

문제

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

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

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

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

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

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

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

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

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

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에 하나의 정수 N(1 ≤ N ≤ 300) 이 주어진다. 이는 지뢰 찾기를 하는 표의 크기가 N*N임을 나타낸다.

다음 N개의 줄의 i번째 줄에는 길이가 N인 문자열이 주어진다.

이 중 j번째 문자는 표에서 i번째 행 j번째 열에 있는 칸이 지뢰가 있는 칸인지 아닌지를 나타낸다.

‘’이면 지뢰가 있다는 뜻이고, ‘.’이면 지뢰가 없다는 뜻이다. ‘’와 ‘.’외의 다른 문자는 입력으로 주어지지 않는다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

최소 몇 번의 클릭을 해야 지뢰가 없는 모든 칸에 숫자가 표시될 것인지 출력한다.

구조화

지뢰가 없는칸( . )을 입력받을 때 리스트에 넣어두고 해당 리스트를 기준으로 코드를 구현했다

1. 먼저, 8방향 탐색을 통해 현재 칸(map[i][j])이 지뢰가 몇 개가 맞닿아 있는지 list에 담아준다.
2. 그리고 방금 구했던 값을 기준으로 리스트를 오름차순 정렬을 했다.
3. 다음, 방문하지 않았고 해당 칸이 0이라면 BFS를 진행한다
4. BFS를 진행하면서 큐에 빼낸 좌표의 값에 지뢰가 몇 개 맞닿아 있는지를 저장해두고
5. 가려는 칸이 방문하지 않았고, 값이 .이라면 큐에 넣어주고 방문처리를 해준다
6. BFS가 끝이 나면, BFS를 타지 않은 하나씩만 남아있는 값들을 다 더해준다.

코드

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

// 파핑파핑 지뢰찾기
public class Solution {
	static int N, ans;
	static char[][] map;
	static boolean[][] isVisited;
	static int[] dr = {-1, 0, 1, 0, -1, 1, 1, -1};
	static int[] dc = {0, 1, 0, -1, 1, 1, -1, -1};
	static List<Coords> list;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t = 1 ; t <= T ; t ++) {
			ans = 0;
			list = new ArrayList<>();
			N = Integer.parseInt(br.readLine());
			map = new char[N][N];
			isVisited = new boolean[N][N];
			for(int i = 0; i < N; i ++) {
				String s = br.readLine();
				for(int j = 0; j < N; j ++) {
					char tmp = s.charAt(j);
					map[i][j] = tmp;
					if(tmp == '.') list.add(new Coords(i, j));
				}
			}

			// .이 담겨있는 리스트에서 8방탐색을 실시
			// map 범위 내 & 해당 칸이 * 라면 n ++, list의 num에 n을 담아줌
			for (int i = 0; i < list.size(); i++)
				list.get(i).num = bombCnt(list.get(i).r, list.get(i).c, 0);

			// n을 기준으로 오름차순 정렬해줌
			Collections.sort(list);

			// .이 담긴 리스트 만큼 반복
			// 방문하지 않았고 해당 칸이 0이라면 bfs 돌림
			for (int i = 0; i < list.size(); i++) {
				if(!isVisited[list.get(i).r][list.get(i).c] && list.get(i).num == 0) {
					bfs(list.get(i).r, list.get(i).c);
					ans++;
				}
			}
			
			// bfs를 타지 않은 남은 . 의 개수를 탐색
			findExtra();

			System.out.println("#"+t+" "+ans);
		}
	}
	
	static void bfs(int i, int j) {
		Queue<Coords> q = new ArrayDeque<>();
		q.offer(new Coords(i, j));
		while(!q.isEmpty()) {
			Coords curr = q.poll();
			isVisited[curr.r][curr.c] = true;

			// 해당 칸 8방탐색후 폭탄 개수를 넣어줌
			bombCnt(curr.r, curr.c, 1);

			if(map[curr.r][curr.c] == '0') {
				for(int d = 0 ; d < 8 ; d ++) {
					int nr = curr.r + dr[d];
					int nc = curr.c + dc[d];

					if(isVaild(nr, nc)) {
						// 가려는 칸을 방문하지 않았고, 값이 .이라면
						if(!isVisited[nr][nc] && map[nr][nc] == '.') {
							q.offer(new Coords(nr, nc));
							isVisited[nr][nc] = true;
						}
					}
				}
			}
		}
	}
	
	static int bombCnt(int i, int j, int mode) {
		int cnt = 0;
		for(int d = 0 ; d < 8 ; d ++) {
			int nr = i + dr[d];
			int nc = j + dc[d];

			if(isVaild(nr, nc) && map[nr][nc] == '*') cnt ++;
		}
		if(mode == 1)
			map[i][j] = (char) ('0' + cnt);
		return cnt;
	}
	
	private static void findExtra() {
        for (int n = 0; n < list.size(); n++) {
            if(map[list.get(n).r][list.get(n).c] == '.') {
                ans++;
            }
        }
    }
	
	static class Coords implements Comparable<Coords>{
		int r;
		int c;
		int num;

		public Coords(int r, int c) {
			this.r = r;
			this.c = c;
		}
		@Override
		public int compareTo(Coords o) {
			return this.num - o.num;
		}
	}
	
	static boolean isVaild(int nr, int nc) {
		return (nr>=0 && nc>=0 && nr<N && nc<N);
	}
}