[SWEA] 1868: 파핑파핑 지뢰찾기 (JAVA)

문제

SW Expert Academy

 

여담

문제를 제대로 읽지 않았다..^^ 주변에 지뢰가 없는 것을 열면 끝이라고 생각했는데, 예시를 보니 "주변에 지뢰가 없는 것을 열었음 → 열은 칸 주변에도 지뢰가 없음 → 연속적으로 해당 칸 열기"를 하는 것이었다. 즉, BFS/DFS 탐색을 통해 푸는 문제였다...ㅎ

 

문제를 제대로 읽고 해석하는 것도 실력이니 꼭..! 문제를 꼼꼼히 읽자

 

풀이

지뢰가 없는 칸을 모두 여는 최소 터치 횟수를 구하는 문제이고, 주변에 지뢰가 없는 것을 열었는데 새로 열은 칸 주변에도 지뢰가 없다면 연속해서 칸을 열어야 한다. 즉, 지뢰가 없는 칸을 여는 최소 터치 횟수 구하기 & 1번의 터치로 주변에 지뢰가 없는 칸을 연속해서 열어야 하므로, BFS 또는 DFS 탐색을 수행하면 된다.

 

문제에서는 지뢰의 여부만 주어지므로, 우선 각각의 칸마다 주변에 위치한 지뢰의 개수를 세야 한다. 그 후, 주변에 지뢰가 없는 칸(bombs[i][j] = 0)을 기준으로 BFS 탐색을 수행하면 된다. 이때, BFS 탐색을 호출한 횟수가 지뢰가 없는 칸을 터치한 횟수와 같다. (1번의 터치로 주변에 지뢰가 없는 칸을 연속해서 열기 때문)

 

주변에 지뢰가 없는 칸들을 모두 열었다면, 이제 주변에 지뢰가 있는 칸들을 하나하나 열어야 한다. 즉, 열어야 하는 칸의 수가 "지뢰가 아닌 칸의 총 수 - 지금까지 열은 칸의 수"이므로, 해당 값과 BFS 탐색을 호출한 횟수를 더해서 출력하면 된다.

 

정리하면 다음과 같다.

1. 주변에 위치하는 지뢰 개수 찾기
2. 주변에 지뢰가 하나도 없고 열지 않은 칸이라면 BFS 탐색하기
   • BFS 탐색 순서
     • 터치한 칸 주변에 위치한 칸들을 모두 열기 (8방향)
     • 만약 새로 연 칸 주변에 지뢰가 없다면, 큐에 넣기 (= 연속해서 칸을 여는 것)
   • BFS 탐색 횟수 = 현재까지 보드를 터치한 횟수
3. 이미 열은 칸과 지뢰가 있는 칸을 제외한 칸은 모두 하나씩 터치해서 열어야 함
   • 터치 최소 횟수 = BFS 탐색 횟수 + (지뢰가 없는 칸의 총 수 - 현재까지 연 칸의 수)

 

말로 설명하다보니 조금 헷갈리게 적은 것 같은데, 문제에서 주어진 예시와 코드를 참고하면 보다 쉽게 이해할 수 있을 것이다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

// 주변에 지뢰가 없으면 해당 칸이 열리면 연속적으로 열림 > BFS 탐색
// 지뢰가 없는 칸들을 다 열었으면 남은 칸은 각각 하나씩 클릭해야 함 > 남은 수 더하기
class Solution {
	static int N, total;
	static char[][] board;
	static int[][] bombs; // 주변에 위치한 지뢰의 개수를 저장하는 배열
	static ArrayList<int[]> nonBomb;
	static boolean[][] visited;
	static int[][] move = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			board = new char[N][N];
			bombs = new int[N][N];
			nonBomb = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				for (int j = 0; j < N; j++) {
					board[i][j] = str.charAt(j);
					if (board[i][j] == '.') // 지뢰가 아닌 칸의 위치 저장하기
						nonBomb.add(new int[] { i, j });
				}
			}

			// 주변의 지뢰 개수 찾기	
			total = nonBomb.size();
			for (int[] pos : nonBomb) {
				int x = pos[0], y = pos[1];
				bombs[x][y] = checkBomb(x, y);
			}

			// 지뢰가 하나도 없으면 옆의 8칸까지 연속해서 열림 → BFS 탐색
			visited = new boolean[N][N];
			int touch = 0;
			for (int[] pos : nonBomb) {
				int x = pos[0], y = pos[1];
				if (bombs[x][y] == 0 && !visited[x][y]) {
					touch++;
					total--;
					bfs(x, y);
				}
			}
            // 최소 클릭 횟수 = BFS 탐색 횟수 + 지뢰가 없고 아직 열리지 않은 칸의 수
			sb.append("#").append(t).append(" ").append(total + touch).append("\n");
		}
		System.out.println(sb.toString());
	}

	static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { x, y });
		visited[x][y] = true;

		while (!queue.isEmpty()) {
			int[] now = queue.poll();

			for (int i = 0; i < 8; i++) {
				int nx = now[0] + move[i][0];
				int ny = now[1] + move[i][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny])
					continue;

				total--;
				visited[nx][ny] = true;
				if (bombs[nx][ny] == 0)
					queue.offer(new int[] { nx, ny });
			}
		}
	}

	static int checkBomb(int x, int y) {
		int bomb = 0;
		for (int i = 0; i < 8; i++) {
			int nx = x + move[i][0];
			int ny = y + move[i][1];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N)
				continue;

			if (board[nx][ny] == '*')
				bomb++;
		}
		return bomb;
	}
}

---