[JAVA]지뢰 찾기 - 델타 배열을 이용한 방법

지뢰찾기류의 문제는 생각보다 여기저기 많다.

처음 이런 델타배열류의 문제를 본 것은 프로그래머스였다.

프로그래머스의 안전지대 문제를 풀었는데, 저 때는 델타 배열의 존재를 몰라서

import java.util.*;
class Solution {
    public int solution(int[][] board) {
        int answer = 0;
        int length = board.length;
        int[][] board2 = new int[length+2][length+2];
        for (int i=0; i<board2.length;i++){
            Arrays.fill(board2[i],0);
        }
        for (int i=0;i<length;i++){
            for (int j=0;j<length;j++){
                if (board[i][j]==1){
                    for (int k=-1;k<=1;k++){
                        for(int l=-1;l<=1;l++){
                            board2[i+k+1][j+l+1] += 1;
                        }
                    }
                }
            }
        }
        for (int i=1;i<=length;i++){
            for (int j=1;j<=length;j++){
                if (board2[i][j]==0) answer++;
            }
        }
        return answer;
    }
}

이런 긴 4중 for문으로 문제를 풀었었다. 물론 문제가 좀 어렵기도 했다.

 

다음은

다음도 이와 비슷한 봉우리 찾기 문제인데, 여기는 친절하게도 한칸씩 미리 늘려서 알려주었다.

public class Main {
    public int solution(int[][] arr) {
        int cnt = 0;
        for (int i=1; i<arr.length-1; i++){
            for (int j=1; j<arr.length-1;j++){
                if ((arr[i-1][j] < arr[i][j])
                        &&(arr[i+1][j]<arr[i][j])
                        &&(arr[i][j+1]<arr[i][j])
                        &&(arr[i][j-1]<arr[i][j])) cnt++;
            }
        }
        return cnt;
    }

문제가 그렇게 복잡하지는 않았는데, 만약 이게 전후좌우, 또는 전후좌우대각선, 또는 

이거 조건식 걸다간 죽어버릴거야

이런 류로 탐색을 해야 한다면 어떨까?

for문을 하루종일 돌리거나, if조건문에만 엄청나게 식을 많이 써서 돌릴 것이다.

이 때 필요한 것이 델타 배열이다.

델타 배열은 간단하다.

일단 먼저 상하좌우 4방향을 탐색해야한다고 생각해보자. 이 때,

int[] dx = {-1,0,0,1};
int[] dy = {0,-1,1,0};

를 만들어 i+dx = nx, i+dy = ny로 놓고 푼다면 내가 있는 좌표의 위치를 찾아볼 수 있다.

더 나아가서 대각선까지 포함하는 8방을 탐색해야한다고 생각해보자.

int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 1, 0, -1, 1, -1, 1, 0};

이 때 for문을 이용해 8번 돌리면 내 주위의 방향을 다 파악할 수 있다.

public char[][] solution(int n, char[][] arr){
        char[][] answer = new char[n][n];
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 1, 0, -1, 1, -1, 1, 0};
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (Character.isDigit(arr[i][j])) {
                    answer[i][j] = '*';
                } else {
                    int tmp = 0;
                    for (int k = 0; k < 8; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx >= 0 && nx < arr.length && ny >= 0 && ny < arr.length) {
                            if (Character.isDigit(arr[nx][ny])) tmp += arr[nx][ny] - '0';
                        }
                    }
                    if (tmp > 10) answer[i][j] = 'M';
                    else answer[i][j] = (char) (tmp + '0');
                }
            }
        }
        return answer;
    }

이렇게 델타 배열을 이용하면, 조건문을 훨씬 편하게 짤 수도 있고,

또 혹시나 위에 그림처럼 8방이 아닌 많은 방향에서도 정확하게 탐색을 할 수 있다.

 

좋아하는 말 중에 E=MC^2라는 말이 있다.

Error = More Code라는 말인데, 델타 배열을 쓰지 않으면 너무 많은 코드로 더 많은 에러를 야기시킬 수 있다.

무엇이 틀린지 한참 고민해야하는것은 덤이다.

 

추가 팁)

1. 다른조건보다 늘 nx, ny의 유효성검사를 해주어야 한다. 그렇지 않으면 ArrayOutOfBoundException 에러가 난다.

2. 가장 안쪽에 for문을 돌 때 break를 걸어주면 더 편하다. 예를 들어 봉우리 문제인 경우, 내 주위 8방향보다 내가 값이 더 커야 하는데, 다른 방향에서의 value가 더 클 때 break를 걸어주면 최대 7번의 for문이 도는것을 절약할 수 있다.