[프로그래머스] 안전지대 - Java(자바)

문제

다음 그림과 같이 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류합니다.

 

지뢰는 2차원 배열 board 에 1로 표시되어있고 board 에는 지뢰가 매설된 지역 1과, 지뢰가 없는 지역 0만 존재합니다.

지뢰가 매설된 지역의 지도 board가 매개변수로 주어질 때, 안전한 지역의 칸 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• board 는 n * n 배열입니다.
• 1 <= n <= 100
• 지뢰는 1로 표시되어 있습니다.
• board 에는 지뢰가 있는 지역 1과 지뢰가 없는 지역 0만 존재합니다.

입출력 예

board	result
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]. [0, 0, 0, 0, 0]]	16
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0]]	13
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]	0

 

---

코드(Java) - 내 코드

class Solution {
    public int solution(int[][] board) {
        int answer = 0;
        int[][] bomb = new int[board.length][board[0].length];
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                bomb[i][j] = board[i][j];
            }
        } //깊은 복사
        
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[i].length; j++) {
                if(board[i][j] == 1) {
                    checkBomb(i, j, bomb);
                }
            }
        }
        
        for(int i=0; i<bomb.length; i++) {
            for(int j=0; j<bomb[i].length; j++) {
                if(bomb[i][j] == 0) {
                    answer++;
                }
            }
        }
        return answer;
    }
    
    void checkBomb(int i, int j, int[][] bomb) {
        int xCalc = 0;
        int yCalc = 0;
        int[] xAround = {0, -1, -1, 1, 0, 1, 1, -1};
        int[] yAround = {-1, -1, 0, -1, 1, 1, 0, 1};
        
        for(int k=0; k<xAround.length; k++) {
            xCalc = j + xAround[k];
            yCalc = j + yAround[k];
            
            if(xCalc >= 0 && yCalc >= 0) {
                if(xCalc < bomb.length && yCalc < bomb[0].length) {
                    bomb[xCalc][yCalc] = 1;
                }
            }
        }
    }
}

풀이 과정

접근방법을 떠올리는데에는 큰 무리가 없었던 문제였지만, 해당 문제를 게시물로 작성하는 이유는 얕은 복사와 깊은 복사의 차이에 대해 기록해두고 싶어서이다. 우선 풀이과정에 대해 적고 아래 "알게된 내용"에서 깊은 복사에 대해 다뤄볼 예정이다.

 

1. board 배열을 돌면서 1(지뢰)을 만났을 때 주변 8개(위, 아래, 좌, 우, 대각선)의 지역을 1로 바꿔줄 배열을 새로 만든다.

   > board 배열 그대로 복사한 새 배열을 만드는 과정에서 깊은 복사가 사용된다. (하단 "알게된 내용" 참고)

2. 지뢰가 있는 위치가 사방의 끝 지점인지 아닌지를 확인한 후, 유효한 위치만 위험지역으로 분류(1로 변경)한다.

3. board 배열을 복사하여 만든 bomb 배열 중 1인 값의 개수를 확인하여 출력한다.

 

코드가 정상적으로 실행된 후, 다른 사람의 코드를 찾아봤는데 이 문제는 크게 더 효율적인 방법은 없는 것 같아서 본 게시물에서는 내 코드만 기록해두었다.

---

알게된 내용

board 배열을 그대로 복사한 bomb 이라는 배열을 만들기 위해, 단순히 int[][] bomb = board < 코드를 통해 복사를 해왔다.

복사한 bomb 배열을 사용하는데 bomb 배열에서 변경된 값이 board 배열에서도 변경되는 문제가 발생했다. 해당 문제에 대한 검색을 하다가 알게된 내용이 "얕은 복사 VS 깊은 복사" 였다.

 

얕은 복사는 단순히 객체의 주소 값만을 복사하는 것이고, 깊은 복사는 객체의 실제값을 새로운 객체로 복사하는 것이다. 즉, 얕은 복사의 경우 여러 객체가 같은 주소를 참조하기 때문에 하나의 값을 변경하면 다른 대상의 값 역시 바뀌는 문제가 발생하는 것이었다.

(메모리 측면에서 본다면, 한 객체로 할 수 있는 일은 하나에서 끝내는 것이 좋기 때문에 상황에 맞는 복사 방법을 사용하는것이 좋다.)

 

아래 코드는 1차원 배열에 대한 얕은 복사를 하는 방법이다.

int[] a = {1, 2, 3, 4};
int[] b = a; // = 는 주소를 이어준다는 의미

아래 코드는 1차원 배열에 대한 깊은 복사를 하는 방법이다. 

int[] a = {1, 2, 3, 4};
int[] b = new int[a.length];
for(int i=0; i<a.length; i++) {
    b[i] = a[i];
}

위와 같이 for문을 돌려서 복사하는 방법 말고도, 자바에서 제공하는 여러 메소드를 활용하는 방법도 있다.

int[] a = {1, 2, 3, 4};

//Object.clone()
int[] b = a.clone(); //가장 보편적인 방법

//Arrays.copyOf()
int[] b = Arrays.copyOf(a, a.length); //처음부터 원하는 지점까지 복사 가능

//Arrays.copyOfRange()
int[] b = Arrays.copyOfRange(a, 1, 3); //복사하고자하는 시작점, 끝점 지정 가능

//System.arraycopy()
int[] b = new int[a.length];
System.arraycopy(a, 0, b, 0, a.length); //지정된 위치에 복사

 

위와 같은 메소드를 활용해서는 2차원 배열에 대한 깊은 복사를 할 수 없다. 위와 같은 방법으로 2차원 배열을 깊은 복사하면, arr[x][y] 중 주소 값만 있는 a[x] 부분만 깊은 복사가 되고 값이 있는 a[x][y] 부분은 깊은 복사가 되지 않는다.

2차원 배열을 깊은 복사하기 위해서는 아래 코드와 같이 for 문을 돌면서 복사하거나 System.arraycopy 를 활용하여 복사를 해줘야한다. 본 게시물에서 사용된 코드를 예시로 들어보자.

int[][] bomb = new int[board.length][board[0].length];

//for문 사용
for(int i=0; i<board.length; i++) {
    for(int j=0; j<board[0].length; j++) {
        bomb[i][j] = board[i][j];
    }
}

//System.arraycopy 메소드 사용
for(int i=0; i<board.length; i++) {
    System.arraycopy(board[i], 0, bomb[i], 0, board[0].length);
}