[쉽게 배우는 자바 프로그래밍] 5장 : 8번 - JAVA[자바]

⊙ 문제

 

다음과 같은 지뢰 찾기 게임 프로그램을 작성하시오. 실행 결과는 '5 10 0.3'을 명령행 인수로 사용한 예이다.

• 프로그램은 3개의 명령행 인수(m, n, p)를 받아들이고, m * n 크기의 배열을 생성해 지뢰를 숨긴다.
• 숨긴 지뢰가 있는 원소는 *로 표시하고 없는 원소는 -로 표시한다. 원소에 지뢰가 있을 확률은 세 번째 명령행 인수인 p이다.
• 지뢰 숨김 여부를 나타내는 2차원 배열을 출력하고, 지뢰를 숨기지 않은 원소를 -대신에 이웃한 지뢰 개수로 채운 2차원 배열도 함께 출력한다.
• 이웃한 지뢰는 상하좌우 및 대각선 원소에 숨긴 지뢰를 의미한다.
• 지뢰 숨긴 지역을 30%로 설정하려면, 난수 발생 정적 함수 Math.random() 값이 0.3보다 적은 원소에 지뢰를 숨긴다.

실제 출력 화면

 

---

 

⊙ 문제 접근 과정

 

문제를 보자마자 접근을 BFS로 해야겠다고 생각했다. 자바 구현 능력이 살짝 부족하여 먼저 C++로 해당 문제를 풀어보았다. 따라서 이 문제의 정답 코드는 JAVA, C++ 두 개이다.

 

배열 칸과 확률을 설정하고, 해당 확률 값보다 값이 적으면 지뢰 설치.

지뢰가 없는 곳은 상하좌우 및 대각선을 탐색하여 지뢰가 주변에 몇 개 숨어있는지 출력해야 한다.

 

 

 

해당 문제는 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색의 알고리즘 개념이 잡혀있지 않다면 푸는데 어려움을 느낄 수 있다.

 

---

 

⊙ 문제 풀이(JAVA)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair{
    int y;
    int x;
    public Pair(int y, int x) {
        this.y = y;
        this.x = x;
    }
}
public class Main {
    static int M = -1;
    static int N = -1;
    static double P = 0;
    static int[][] random;
    static String[][] first;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        P = Double.parseDouble(st.nextToken());
        random = new int[M][N];
        arr = new int[M][N];
        first = new String[M][N];
        P=P*100;

        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                int num = (int)(Math.random()*100);
                random[i][j]=num;
            }
        }

        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                if(P>random[i][j]) {
                    first[i][j]="*";
                } else {
                    first[i][j]="-";
                }
            }
        }


        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                bfs(i,j);
            }
        }

        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                if(first[i][j]=="*") {
                    System.out.print(first[i][j]+" ");
                } else {
                    System.out.print(arr[i][j]+" ");
                }
            }
            System.out.println();
        }

    }
    static void bfs(int y,int x) {
        int dx[] = {1,0,-1,0,1,-1,1,-1};
        int dy[] = {0,1,0,-1,1,1,-1,-1};
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(y,x));
        while(!q.isEmpty()) {
            Pair p = q.poll();
            for(int i=0;i<8;i++) {
                int na = p.y + dx[i];
                int nb = p.x + dy[i];
                if(0<=na && 0<=nb && na<M && nb < N && first[na][nb]=="*") {
                    arr[p.y][p.x]++;
                }
            }
        }
    }
}

 

 

---

⊙ 문제 풀이(C++)

 

#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>

using namespace std;
#define MAX 21


int M,N;
double P;
int random[MAX][MAX];
string first[MAX][MAX];
int arr[MAX][MAX] = {0,};
int dx[] = {1,0,-1,0,1,-1,1,-1};
int dy[] = {0,1,0,-1,1,1,-1,-1};
queue<pair<int,int>> q;

void bfs(int y, int x) {
    q.push({y,x});
    while(!q.empty()) {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        for(int i=0;i<8;i++) {
            int na = a + dx[i];
            int nb = b + dy[i];
            if(0<=na && 0<=nb && na<MAX && nb < MAX && first[na][nb]=="*") {
                arr[a][b]++;
            }
        }
    }
} 

int main() {
    srand(time(NULL));

    cin >> M >> N >> P;
    P*=100;

    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            int num = rand()%100+1;
            random[i][j] =num;
        }
    }

    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            if(P>random[i][j]) {
                first[i][j]="*";
            } else {
                first[i][j]="-";
            }
        }
    }

    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            bfs(i,j);
        }
    }

    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            if(first[i][j]=="*") {
                cout <<first[i][j] << " ";
            } else {
                cout << arr[i][j] << " ";
            }
        }
        cout << "\n";
    }
}

---

⊙ 결과

 

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!