[SWEA] 1868번 : 파핑파핑 지뢰찾기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc

SW Expert Academy

 

음 아이디어가 떠오르지않았다.

처음에 테케 중에 1번은 나왔는데 2번은 안나왔던 이유

자꾸 13이 나오드라구요. 

최소값이 아니라 전체를 다 돌았기 때문이다. 

 

https://yoon-e.tistory.com/12

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

 

코드가 똑같진않지만, 최소값을 어떻게 해야할까...고민하는 아이디어만 받아서 풀었다.

최소로 하려면 0인 곳을 먼저 터트리고, 남은 값을 채워주면 된다. 

 

우선 주변에 지뢰 있는지 없는지 부터 체크를 해주어야한다. 

개수를 세서 char 형으로 반환했다.

사실 char 바꾸는거 return cnt+'0'; 이러고 있었다. 진짜 미친건가. 배고픈건가...

static char cal(int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                if (map[nx][ny] == '*') {
                    cnt++;
                }
            }
        }
        return (char) (cnt+'0');
    }

 

그리고 0 이면 0으로 채우고, 또 폭발해야한다. 나는 bfs 를 사용했다. 파고드는게 아니라 주변을 폭발시키는거니깐..? 

주변 지뢰 개수를 세서 0일때만 q에 넣어주면 된당. 

static void bfs(int x, int y) {
        // 연쇄적 폭발
        // if(cal==0) 이면 주변 다 0 으로 채우고
        // 큐에 넣기
        // 빼면서 또 세고 0 이면 연쇄 폭발
        Queue<Pair> q = new ArrayDeque<>();
        v[x][y]=1;
        q.add(new Pair(x, y));

        while(!q.isEmpty()) {
            Pair cur = q.poll();
            int cx = cur.x;
            int cy = cur.y;
            for(int i=0;i<8;i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if(nx>=0 && nx<n && ny>=0 && ny<n && v[nx][ny]==0 && map[nx][ny]!='*') {
                    char cnt = cal(nx, ny);
                    map[nx][ny] = cnt;
                    v[nx][ny]=1;
                    if(cnt=='0'){
                        // 다시 q 에 넣어
                        q.add(new Pair(nx, ny));
                    }
                }
            }
        }

    }

 

전체코드는 아래와 같다. 

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

class Solution {

    static int n, ans;
    static int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    static int dy[] = {1, 1, 1, 0, -1, -1, -1, 0};
    static int v[][];
    static char map[][];

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {

            n = Integer.parseInt(br.readLine());

            map = new char[n][n];
            v = new int[n][n];
            for (int i = 0; i < n; i++) {
                String line = br.readLine();
                for (int j = 0; j < n; j++) {
                    map[i][j] = line.charAt(j);
                }
            }

            // 지회가 있는 칸 -> 파핑 파핑
            // 지뢰가 없는 칸 -> 변이 맞닿아 있거나 꼭지점이 맞닿아 있는 최대 8칸에 대해
            // 몇 개의 지뢰가 있는 지 0-8사이의 숫자로 클릭한 칸에 표시

            // 지뢰 : *
            // 없는 칸 : .
            // 클릭한 지뢰가 없는 칸 : c
            ans = 0;
            // 지뢰가 없는 칸 부터 늘리고
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    char cnt = cal(i, j);
                    if (cnt == '0' && v[i][j] == 0 && map[i][j] == '.') {
                        map[i][j] = cnt;
                        bfs(i, j);
                        ans++;
                    }
                }
            }

            // 지뢰가 있는 칸 늘려
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (v[i][j] == 0 && map[i][j] == '.') {
                        map[i][j] = cal(i, j);
                        ans++;
                    }
                }
            }

            System.out.println("#" + tc + " " + ans);
        }

        br.close();

    }

    static void bfs(int x, int y) {
        // 연쇄적 폭발
        // if(cal==0) 이면 주변 다 0 으로 채우고
        // 큐에 넣기
        // 빼면서 또 세고 0 이면 연쇄 폭발
        Queue<Pair> q = new ArrayDeque<>();
        v[x][y]=1;
        q.add(new Pair(x, y));

        while(!q.isEmpty()) {
            Pair cur = q.poll();
            int cx = cur.x;
            int cy = cur.y;
            for(int i=0;i<8;i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if(nx>=0 && nx<n && ny>=0 && ny<n && v[nx][ny]==0 && map[nx][ny]!='*') {
                    char cnt = cal(nx, ny);
                    map[nx][ny] = cnt;
                    v[nx][ny]=1;
                    if(cnt=='0'){
                        // 다시 q 에 넣어
                        q.add(new Pair(nx, ny));
                    }
                }
            }
        }

    }

    static char cal(int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                if (map[nx][ny] == '*') {
                    cnt++;
                }
            }
        }
        return (char) (cnt+'0');
    }

}

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}