※문제 출처
https://swexpertacademy.com/main/talk/solvingClub/problemView.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
※BFS
넓이 우선 탐색(Breadth First Search) . 특정 노드(칸)를 기준으로 같은 깊이의 노드(칸)으로 탐색 범위를 넓혀가는 방법.
Queue 자료형을 활용해서 구현하며 주로 경로 탐색 등에서 사용된다.
[문제]
‘파핑 파핑 지뢰 찾기’라는 유명한 게임이 있다. 이 게임은 RXC 크기의 표를 이용하는 게임인데,
표의 각 칸에는 지뢰가 있을 수도 있고 없을 수도 있다.
표의 각 칸을 클릭했을 때, 그 칸이 지뢰가 있는 칸이라면 ‘파핑 파핑!’이라는 소리와 함께 게임은 끝난다.
지뢰가 없는 칸이라면 변이 맞닿아 있거나 꼭지점이 맞닿아 있는 최대 8칸에 대해 몇 개의 지뢰가 있는지가 0에서 8사이의 숫자로 클릭한 칸에 표시된다.
만약 이 숫자가 0이라면 근처의 8방향에 지뢰가 없다는 것이 확정된 것이기 때문에 그 8방향의 칸도 자동으로 숫자를 표시해 준다.
실제 게임에서는 어떤 위치에 지뢰가 있는지 알 수 없지만, 이 문제에서는 특별히 알 수 있다고 하자.
지뢰를 ‘*’로, 지뢰가 없는 칸을 ‘.’로, 클릭한 지뢰가 없는 칸을 ‘c’로 나타냈을 때 표가 어떻게 변화되는지 나타낸다.
세 번째 예에서는 0으로 표시 될 칸들과 이와 인접한 칸들이 한 번의 클릭에 연쇄적으로 숫자가 표시된 것을 볼 수 있다.
파핑 파핑 지뢰 찾기를 할 때 표의 크기와 표가 주어질 때, 지뢰가 있는 칸을 제외한 다른 모든 칸의 숫자들이 표시되려면 최소 몇 번의 클릭을 해야 하는지 구하는 프로그램을 작성하라.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에 하나의 정수 N(1 ≤ N ≤ 300) 이 주어진다. 이는 지뢰 찾기를 하는 표의 크기가 N*N임을 나타낸다.
다음 N개의 줄의 i번째 줄에는 길이가 N인 문자열이 주어진다.
이 중 j번째 문자는 표에서 i번째 행 j번째 열에 있는 칸이 지뢰가 있는 칸인지 아닌지를 나타낸다.
‘*’이면 지뢰가 있다는 뜻이고, ‘.’이면 지뢰가 없다는 뜻이다. ‘*’와 ‘.’외의 다른 문자는 입력으로 주어지지 않는다.
[출력]
최소 몇 번의 클릭을 해야 지뢰가 없는 모든 칸에 숫자가 표시될 것인지 출력한다.
[풀이 방법]
문제 자체는 어릴 때 자주 하던 지뢰찾기라 이해가 어렵지는 않을 것이다. 고려해야할 점은,
1. 각 점마다 8방 탐색을 진행한뒤 지뢰가 하나도 없어야 다음 칸으로 탐색을 진행한다는 점.
2. 모든 칸을 누르는 "최소 클릭수"를 묻고 있기 때문에 주변 지뢰 수가 0인 칸을 최대한 많이 눌러야 한다는 점. 이다.
이 부분에서 DFS로 푸는 방법이 더 쉬울 수도 있지만 BFS 연습 겸 더 직관적인 BFS로 풀이를 진행했다.
즉, 맵 전체를 2번 돌아야 한다. 처음 돌때는 지뢰수가 0인 칸만을 클릭해서 최대한 탐색한 칸을 늘린 뒤, 두번째 돌 때 탐색되지 않는 칸을 클릭해주면 최소 클릭 수를 구할 수 있다.
import java.io.*;
import java.util.*;
public class Solution {
static char[][] dmap;
static boolean[][] v;
static int N;
static int[] di = {-1,-1,0,1,1,1,0,-1}; //상 -> 상좌 순으로 팔방탐색
static int[] dj = {0,1,1,1,0,-1,-1,-1};
static int ans;
//주변에 폭탄이 있는지 확인
static public int bomb(int r, int c) {
int cnt = 0;
for(int d=0;d<8;d++) {
int ni = r+di[d];
int nj = c+dj[d];
if(ni>=0 &&ni<N && nj>=0 && nj<N) {
if (dmap[ni][nj] == '*') {
cnt +=1;
}
}
}
return cnt;
}
static public void bfs(int r, int c) {
ArrayDeque<char[]> deq = new ArrayDeque<>();
v[r][c] = true;
deq.offer(new char[] {(char) (r+'0'),(char) (c+'0')});
//입력을 받을 때 char[] 로 받아와서 int로 바꿔주는 과정이 필요
while(!deq.isEmpty()) {
char[] oj = deq.poll();
int i = oj[0]-'0';
int j = oj[1]-'0';
int cnt = bomb(i,j);
dmap[i][j] = (char)(cnt+'0');
if (cnt>0) {
continue;
}
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 && v[ni][nj] == false && dmap[ni][nj]!='*') {
v[ni][nj] = true;
deq.offer(new char[] {(char)(ni+'0'),(char)(nj+'0')});
}
}
}
}
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine().trim());
for(int tc = 1;tc<=T;tc++) {
ans = 0;
N = Integer.parseInt(br.readLine().trim());
dmap = new char[N][N];
v = new boolean[N][N];
for(int i = 0;i<N;i++) {
StringTokenizer st = new StringTokenizer(br.readLine().trim());
String line = st.nextToken();
for(int j=0;j<N;j++) {
dmap[i][j] = line.charAt(j);
}
}
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(bomb(i,j) ==0 && dmap[i][j] != '*' && v[i][j] == false) {
//눌러야하는 최소 횟수를 구하는 문제이기 때문에
//처음에는 최대한 탐색을 넓게 할수 있는 칸을 눌러야한다
//즉, 주변에 폭탄수가 0이라 계속 탐색을 할 수 있는 칸!
ans+=1;
bfs(i,j);
}
}
}
//폭탄수가 0인칸을 누르면 주변에 폭탄이 있을때까지 계속 탐색해나가기 때문에
//위 처리를 마친 후에도 눌러지지 않은 칸은 각 칸마다 클릭 수를 증가시켜야 한다.
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(dmap[i][j] == '.') {
dmap[i][j] = (char)(bomb(i,j)+'0');
v[i][j] = true;
ans +=1;
}
}
}
sb.append("#").append(tc).append(" ").append(ans).append("\n");
}
System.out.println(sb);
}
}