[SWEA] 파핑파핑 지뢰찾기 문제풀이
문제
문제 링크 바로가기
https://swexpertacademy.com/main/talk/solvingClub/problemSubmitDetail.do
‘파핑 파핑 지뢰 찾기’라는 유명한 게임이 있다. 이 게임은 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부터 시작한다)를 출력하고,
최소 몇 번의 클릭을 해야 지뢰가 없는 모든 칸에 숫자가 표시될 것인지 출력한다.
문제 간략화
만약 클릭을 했는데, 클릭 한 결과가 0이라면
연쇄로 근처는 클릭 없이 자동으로 반환이되고,
또 0이라면 계속 이 과정의 반복이다.
그렇다면 0의 결과가 나왔다면 해당 8방향을 전부 Queue에 넣고,
Queue가 빌 때까지 while문을 반복한다.
그리고 0이 나올때마다 해당 사항을 반복한다.
남은 클릭이 더이상 필요 없을만큼 계속 반복한다.
문제 풀이
우선은 8방향에 대한 배열을 선언
static int[][] dirs = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1},
{-1, -1}, {-1, 1}, {1, -1}, {1, 1}
};우선은 해당 칸에서 '*'로 입력을 받으면,
지뢰인 것을 알 수 있다.
어차피 모든 칸이 숫자로 채워져야하므로, 별을 유효하지 않은 -1로 선언한다.
정수 2차원 배열의 adj를 따로 선언하기
- 근처의 지뢰 찾기
static void computeAdj() {
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (board[r][c] == '*') {
adj[r][c] = -1; // 지뢰 표시
continue;
}
int cnt = 0;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (in(nr, nc) && board[nr][nc] == '*') {
cnt++;
}
}
adj[r][c] = cnt;
}
}
}cnt++는 그만큼의 지뢰 숫자를 카운트 하는 것입니다.
adj[r][c]에 해당 지뢰의 숫자 카운트를 채웁니다.
- BFS의 과정으로 0이 나올 경우 Queue에 담는 과정
static void bfsOpen(int sr, int sc) {
Queue<int[]> q = new ArrayDeque<>();
visited[sr][sc] = true; // 시작점 방문 처리
q.offer(new int[]{sr, sc});
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
// 현재 칸이 0이면 주변을 탐색하여 큐에 추가
// (adj[r][c] > 0 인 칸은 여기서 주변 탐색을 멈춥니다.)
if (adj[r][c] == 0) {
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
// 유효한 범위이고, 지뢰가 아니며, 아직 방문하지 않은 칸
if (in(nr, nc) && board[nr][nc] != '*' && !visited[nr][nc]) {
visited[nr][nc] = true; // 방문 처리 (0이 아닌 숫자 칸도 방문 처리됨)
// 0인 경우에만 추가로 탐색하기 위해 큐에 넣음
if (adj[nr][nc] == 0) {
q.offer(new int[]{nr, nc}); // 올바른 좌표 사용
}
}
}
}
}
}if (adj[r][c] == 0) {을 통하여 0에 대해서만 queue에 넣는 대상으로 취급하고, 0이 아니라면 queue에 집어넣을 필요가 없습니다.
이제 아직도 처리하지 못한 남은 칸들에 대하여 클릭을 함으로써 처리
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == '.' && !visited[i][j]) {
visited[i][j] = true;
click++;
}
}
}전체를 탐방하면서 아직 클릭되지 않았고, .으로 남아있을 경우 클릭 처리를 하면서 나머지만 세어주면 된다.
- 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Solution {
static int N;
static char[][] board;
static boolean[][] visited;
static int click;
static int[][] adj; // 인접 지뢰 수
static int[][] dirs = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1},
{-1, -1}, {-1, 1}, {1, -1}, {1, 1}
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine().trim());
board = new char[N][N];
visited = new boolean[N][N];
adj = new int[N][N];
click = 0;
for (int i = 0; i < N; i++) {
String s = br.readLine().trim();
for (int j = 0; j < N; j++) {
board[i][j] = s.charAt(j);
}
}
// 1) 인접 지뢰 수 미리 계산
computeAdj();
// 2) adj==0 인 안전 칸부터 BFS로 열기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == '.' && !visited[i][j] && adj[i][j] == 0) {
bfsOpen(i, j);
click++;
}
}
}
// 3) 남은 안전 칸은 각 한 번의 클릭
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == '.' && !visited[i][j]) {
// 숫자(>0) 칸
visited[i][j] = true;
click++;
}
}
}
System.out.println("#" + tc + " " + click);
}
}
/**
* 근처 지뢰 찾기
*/
static void computeAdj() {
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (board[r][c] == '*') {
adj[r][c] = -1; // 지뢰 표시
continue;
}
int cnt = 0;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (in(nr, nc) && board[nr][nc] == '*') cnt++;
}
adj[r][c] = cnt;
}
}
}
static void bfsOpen(int sr, int sc) {
Queue<int[]> q = new ArrayDeque<>();
visited[sr][sc] = true; // 시작점 방문 처리
q.offer(new int[]{sr, sc});
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
// 현재 칸이 0이면 주변을 탐색하여 큐에 추가
// (adj[r][c] > 0 인 칸은 여기서 주변 탐색을 멈춥니다.)
if (adj[r][c] == 0) {
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
// 유효한 범위이고, 지뢰가 아니며, 아직 방문하지 않은 칸
if (in(nr, nc) && board[nr][nc] != '*' && !visited[nr][nc]) {
visited[nr][nc] = true; // 방문 처리 (0이 아닌 숫자 칸도 방문 처리됨)
// 0인 경우에만 추가로 탐색하기 위해 큐에 넣음
if (adj[nr][nc] == 0) {
q.offer(new int[]{nr, nc}); // 올바른 좌표 사용
}
}
}
}
}
}
static boolean in(int r, int c) {
return 0 <= r && r < N && 0 <= c && c < N;
}
}