파핑파핑 지뢰찾기
1. 문제 접근 방법 및 아이디어
이 문제의 핵심은 “어떤 칸을 먼저 눌러야 이득인가?”를 판단하는 것입니다.
- 아이디어
- 지뢰찾기에서 클릭 한 번으로 가장 많은 칸을 밝힐 수 있는 경우는 주변 8방향에 지뢰가 없는 칸(0칸)을 눌렀을 때입니다.
- 접근 순서
- 모든 빈칸(‘.’)에 대해 주변 8방향의 지뢰 개수를 미리 파악합니다.
- 주변 지뢰가 0개인 칸들을 먼저 찾아 클릭합니다.
- BFS/DFS를 통해 연쇄적으로 밝혀지는 모든 칸을 방문 처리합니다.
- 0인 칸들을 모두 처리한 후에도 여전히 방문하지 않은 빈칸들은 직접 한 번 씩 클릭해야 줘야 합니다.
2. 필요 개념 및 알고리즘
- BFS 또는 DFS
- 특정 칸을 눌렀을 때 그 주변으로 퍼져나가는 연쇄 반응은 그래프 탐색의 전형적인 형태입니다.
- 숫자 0인 칸은 인접한 8방향의 칸을 모두 탐색하고, 그 칸들 중 또 0이 있다면 다시 확산된다 조건은 전형적인 탐색의 형태를 띠고 있습니다.
- 그리디
- 숫자 1 이상인 칸을 먼저 누르면 딱 그 칸만 밝혀집니다.
- 하지만 0인 칸을 누르면 수 많은 칸이 한꺼번에 밝혀집니다.
- 즉, 0인 칸을 최대한 먼저 다 눌러버리는 것이 전체 클릭 횟수를 줄이는 최적의 선택입니다.
3. 실수하는 포인트
- BFS 방문 처리
- 0인 칸만 큐에 넣어야 하지만, **방문 체크는 0이 아닌 주변 칸(연쇄로 인해 밝혀지는 숫자 칸)에도 반드시 해줘야 합니다.
- 만약에 그렇게 하지 않으면 나머지 계산 단계에서 중복 카운트가 발생합니다
4. 코드 풀이
4.1 좌표 클래스 선언
static class Point {
int r, c;
public Point(int r, int c) {
super();
this.r = r;
this.c = c;
}
}
- 좌표를 표현한 클래스입니다
int[]를 사용해도 되지만 직관적이기 않아서 클래스를 선언했습니다.
4.2 8방향 지뢰 측정 함수
static void calMap(int r, int c) {
int cnt = 0; // 주변 지뢰의 수
// 8방향 탐색
for (int i = 0; i < 8; i++) {
// 다음 좌표
int nr = r + dr[i];
int nc = c + dc[i];
// 범위에 벗어나면 다음으로 넘어간다.
if (!(0 <= nr && nr < N && 0 <= nc && nc < N))
continue;
// 지뢰라면 측정한다.
if (map[nr][nc] == '*')
cnt++;
}
// 주변에 지뢰가 없으면 리스트에 추가한다.
if (cnt == 0)
zerolist.add(new Point(r, c));
// 지뢰 측정 완료
map2[r][c] = cnt;
} // 지뢰 측정 함수 종료
- 주변 8 방향을 측정하면서 지뢰가 없는 칸의 좌표를 리스트에 추가합니다.
4.2.1 주변 지뢰 측정 처리
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == '.') {
calMap(i, j);
}
}
}
- 빈칸에 해당하는 주변 8방향을 탐색합니다.
4.3 연쇄 반응 함수
static void bfs(int r, int c) {
// BFS용 큐
ArrayDeque<Point> q = new ArrayDeque<>();
visited[r][c] = true;
result++;
q.offer(new Point(r, c));
// 더 이상 방문할 곳이 없을 떄까지 반복
while (!q.isEmpty()) {
// 현재 좌표
Point cur = q.poll();
int cr = cur.r;
int cc = cur.c;
// 8방향 탐색
for (int i = 0; i < 8; i++) {
// 다음 좌표
int nr = cr + dr[i];
int nc = cc + dc[i];
// 범위에 벗어나면 다음으로 넘어간다.
if (!(0 <= nr && nr < N && 0 <= nc && nc < N))
continue;
// 지뢰면 다음으로 넘어간다.
if (map2[nr][nc] == -1)
continue;
// 이미 방문한 곳은 다음으로 넘어간다.
if (visited[nr][nc])
continue;
// 0인 곳만 연쇄한다.
if (map2[nr][nc] == 0) {
q.offer(new Point(nr, nc));
}
visited[nr][nc] = true;
}
}
} // 연쇄 반응 함수 종료
- 0인 칸만 큐에 넣어야 하지만, 방문 체크는 0이 아닌 주변 칸(연쇄로 인해 밝혀지는 숫자 칸)에도 반드시 해줘야 합니다.
4.3.1 연쇄 반응 처리
for (Point it : zerolist) {
// 이미 방문한 곳은 넘어간다.
if (visited[it.r][it.c])
continue;
bfs(it.r, it.c);
}
- 숫자 0인 리스트에 있는 좌표에서 측정합니다.
- 방문하지 않은 좌표만 측정합니다.
4.4 나머지 계산
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 지뢰인 곳은 다음으로 넘긴다.
if(map2[i][j] == -1)
continue;
// 이미 방문한 곳은 다음으로 넘긴다.
if(visited[i][j])
continue;
result++;
}
}
- 지뢰를 제외하고, 방문하지 않은 빈 칸을 계산합니다.
4.5 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
public class Solution {
static int N; // 표의 크기
static char map[][]; // 표의 정보
static int map2[][]; // 지뢰 측정 정보
static int result; // 최소 클릭 횟수
static int dr[] = { -1, 1, 0, 0, -1, 1, -1, 1 }; // 행 방향 배열
static int dc[] = { 0, 0, -1, 1, 1, -1, -1, 1 }; // 열 방향 배열
static ArrayList<Point> zerolist; // 주변에 지뢰가 없는 좌표 리스트
static boolean visited[][]; // 방문 체크 배열
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine().trim());
// tc 수행
for (int tc = 1; tc <= T; tc++) {
// N 입력
N = Integer.parseInt(br.readLine().trim());
// 초기화
map = new char[N][N];
visited = new boolean[N][N];
result = 0;
zerolist = new ArrayList<>();
map2 = new int[N][N];
// 지뢰 측정 맵 초기화
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map2[i][j] = -1;
}
}
// 표의 정보 입력
for (int i = 0; i < N; i++) {
String row = br.readLine();
for (int j = 0; j < N; j++) {
map[i][j] = row.charAt(j);
}
}
// 주변 지뢰 측정 처리
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == '.') {
calMap(i, j);
}
}
}
// 연쇄 반응
for (Point it : zerolist) {
// 이미 방문한 곳은 넘어간다.
if (visited[it.r][it.c])
continue;
bfs(it.r, it.c);
}
// 나머지 계산
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 지뢰인 곳은 다음으로 넘긴다.
if(map2[i][j] == -1)
continue;
// 이미 방문한 곳은 다음으로 넘긴다.
if(visited[i][j])
continue;
result++;
}
}
// 출력 내용 추가
sb.append("#" + tc + " " + result + "\n");
} // tc 종료
// 출력
System.out.println(sb);
} // 메인 종료
// 좌표 클래스
static class Point {
int r, c;
public Point(int r, int c) {
super();
this.r = r;
this.c = c;
}
}
// 8방향 지뢰 측정 함수
static void calMap(int r, int c) {
int cnt = 0; // 주변 지뢰의 수
// 8방향 탐색
for (int i = 0; i < 8; i++) {
// 다음 좌표
int nr = r + dr[i];
int nc = c + dc[i];
// 범위에 벗어나면 다음으로 넘어간다.
if (!(0 <= nr && nr < N && 0 <= nc && nc < N))
continue;
// 지뢰라면 측정한다.
if (map[nr][nc] == '*')
cnt++;
}
// 주변에 지뢰가 없으면 리스트에 추가한다.
if (cnt == 0)
zerolist.add(new Point(r, c));
// 지뢰 측정 완료
map2[r][c] = cnt;
} // 지뢰 측정 함수 종료
// 연쇄 반응 함수
static void bfs(int r, int c) {
// BFS용 큐
ArrayDeque<Point> q = new ArrayDeque<>();
visited[r][c] = true;
result++;
q.offer(new Point(r, c));
// 더 이상 방문할 곳이 없을 떄까지 반복
while (!q.isEmpty()) {
// 현재 좌표
Point cur = q.poll();
int cr = cur.r;
int cc = cur.c;
// 8방향 탐색
for (int i = 0; i < 8; i++) {
// 다음 좌표
int nr = cr + dr[i];
int nc = cc + dc[i];
// 범위에 벗어나면 다음으로 넘어간다.
if (!(0 <= nr && nr < N && 0 <= nc && nc < N))
continue;
// 지뢰면 다음으로 넘어간다.
if (map2[nr][nc] == -1)
continue;
// 이미 방문한 곳은 다음으로 넘어간다.
if (visited[nr][nc])
continue;
// 0인 곳만 연쇄한다.
if (map2[nr][nc] == 0) {
q.offer(new Point(nr, nc));
}
visited[nr][nc] = true;
}
}
} // 연쇄 반응 함수 종료
} // 메인 클래스