안전지대 찾기

문제설명

---

Solution

우선 코드를 짜기 전에 수행 해야할 필수적인 기능과 예외사항이 뭔지 생각해야한다.

필수적인 기능

1. 지뢰를 배열 조사를 통해 찾는다.
2. 지뢰 근처를 -1로 표현한다.
   
   

예외사항

1. -1로 변환 하는데 이미 1이 존재하면 변환하지 않는다.
2. 인덱스의 범위를 벗어난 경우를 처리한다.

예외사항을 처리하는것이 주 목표가 될 것 같다.
해당 문제에서 Solution 함수가 매개변수를 어떻게 받는지 확인 해보자.

	class Solution {
    public int solution(int[][] board) {
        int answer = 0;
        
        return answer;
    }
}

2차원배열을 가지고 지뢰를 찾아야 하는데, 일단 알고리즘에서 나는 2차원 배열을 좋아하지 않는다,,,
문제에 2차원배열이 끼면은 기본적으로 2중 for문으로 인해 시간복잡도가 O(n^2)가 나오기 때문에 2차원배열을 탐색할때 2중 for문을 사용하지 않는 코드를 짜 보겠다.

[Object 1] 1차원 배열처럼

for문 을 만들기 위해 우선은 2차원 배열의 크기를 확인해야 한다.
고정 크기 배열이므로, 2차원 배열 board가 1차원 배열들을 몇개 가졌는지와 각 1차원 배열들의 크기가 얼마인지를 확인하면 된다.

	board.length; //1차원 배열을 몇개 가지는지
    board[0].length; //각 1차원 배열의 크기가 몇인지

1차원 배열을 몇개 가졌는가와 각 1차원 배열의 크기2차원 고정배열를 곱하면 2차원 배열의 size를 구할 수 있다.

2중 for문을 사용하지 않고 board 배열을 탐색하는 방법은
연산자 %,/ 를 사용 하는 것이다.
(원리는 곰곰히 잘 생각하고 보면 이해 될 것임)

	(...)
    
    int row,col,answer = 0;
        
        for(int i = 0; i < board.length * board[0].length; i++){
            row = i / board[0].length;
            col = i % board[0].length;
            System.out.println(board[row][col]); 
        }
        
    (...)

자, 이제 문제를 본격적으로 풀 준비는 끝났다.
저기 println 부분은 삭제하고 필수적인 기능을 추가 해보자.

[Object 2] if문을 통한 예외처리

필수적인 기능은 지뢰(1)가 있는 곳을 찾고 그 주변을 -1로 채워주는 것이다.

• if문을 사용해서 배열에 1이 있는 곳을 찾는다.
• 1을 찾은 곳의 row와 col이 몇인지 이용해서 -1을 채워준다.

	(...)
    
    	int row,col,answer = 0;
        
        for(int i = 0; i < board.length * board[0].length; i++){
            row = i / data[0].length;
            col = i % data[0].length;
            if(board[row][col] == 1)
            	//지뢰가 위치한 행의 위에 행
                board[row-1][col] = -1;
                board[row-1][col-1] = -1;
                board[row-1][col+1] = -1;
            	
                //지뢰가 위치한 행
                board[row][col-1] = -1;
                board[row][col+1] = -1;
                
                //지뢰가 위치한 행의 다음 행
                board[row+1][col] = -1;
                board[row+1][col-1] = -1;
                board[row+1][col+1] = -1;
        }

    (...)

일단 뼈대가 될 기본적인 메카니즘은 이러하다.
여기서 문제는 예외처리 부분이다.
만약 첫번째 행이면 지뢰가 위치한 행의 위는 없는 곳이고 오류가 뜰 것이다.
만약 첫번째 열에 존재하는 지뢰라면 그 지뢰 전에 있는 공간은 없어서 오류가 뜰 것이다.

이 모든 처리를 if문으로 해결 하겠다.
일단 반복되는 구문이 많으니 -1로 변환해주는 함수를 만들겠다.

	void insertUnsafe(int[][] board, row, col){
        
            board[row][col - 1] = -1;
        
            board[row][col + 1] = -1;
        
            board[row][col] = -1;
    }

지뢰가 영향을 주는 row들에 속한 row 인덱스,col 인덱스를 넘겨주면
해당 함수는 col 부분에서 지뢰가 영향을 주는 곳에 -1 처리를 하는 일을 한다.

자, 여기서 예외처리를 한다. 아까 말했듯이 -1 처리를 하려는 곳이 맨 왼쪽에 있는 경우에는 board[row][col-1]을 수행하면 안된다. ( 오른쪽도 마찬가지 )

그리고 -1처리를 하려면 지뢰가 있는 곳인지 아닌지도 꼭 확인해야 한다.

" 왜? 그냥 어처피 안전지대아니니까 상관없지 않나? "

전혀 아니다. 만약에 다음행에 지뢰가 또 있다면 그 지뢰가 속한 행의 다음 행에 또 -1 처리를 해야하는 작업이 필요한데, 지뢰를 -1로 바꿔버리면 그 작업을 수행하지 못하고 본래 존재하는 안전지대의 갯수보다 더 많은 결과 값을 내게 된다.

그 모든 경우를 처리한 완전한 코드

	(...)
     row = i / board[0].length;
     col = i % board[0].length;
     	if(board[row][col] == 1){
            if(row > 0)
                //맨 위에 붙어 있지 않는 경우에만
                insertUnsafe(board, row-1, col);
                    
                insertUnsafe(board, row, col);
                
            if(row < board.length-1)
                //맨 아래에 붙어 있지 않는 경우에만
                insertUnsafe(board, row+1, col);
    (...)

	(...)
    void insertUnsafe(int[][] board, row, col){
        
        if(col > 0 && board[row][col-1] == 0) 
            //맨왼쪽에 붙어있지 않는 경우에만 + 지뢰가 없는 경우만
            board[row][col - 1] = -1;
        
        if(col < board[0].length-1  && board[row][col+1] == 0)
            //맨오른쪽에 붙어있지 않는 경우에만 + 지뢰가 없는 경우만
            board[row][col + 1] = -1;
        
        if(board[row][col] == 0) 
            //지뢰가 위치한 장소가 아니면 -1
            board[row][col] = -1;
    }

해당 insertUnsafe(col 관련해서 -1 입력) 함수는 main에서 row 예외처리에 따라 호출 해준다.

이제 저 작업들을 하면 -1이 존재해야할 위치에 존재하게 되고
정상적으로 0의 개수(안전지대 개수)가 잘 나올 것이다.