[코딩테스트연습] 코딩테스트 입문 > Lv.0 안전지대

문제 설명

---

문제 풀이

[try1]

class Solution {
    public int solution(int[][] board) {
        int answer = 0;
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                System.out.println("("+i+","+j+") "+board[i][j]);
            }
        }
        return answer;
    }
}

 

우선 각 원소의 위치를 i,j로 얻고 그 값을 출력해보았다.

이제 이 값이 1일 경우, 그 주변인 상하좌우를 위험지역으로 분류해야한다.

여기서 주의해야 할 부분이 무엇이 있을 지 생각해 보았다!

 

1. 가장자리의 경우, 더 이상 위험 지역으로 분류될 공간이 없다.

예시) i==0 또는 i==board.length-1 또는 j==0 또는 j==board[i].length 같은 좌표인 값을 주의하자.

 

2. 지뢰가 한 칸 옆일 경우, 지뢰인 부분은 위험 지역으로 분류되지 않는다.

지뢰의 좌표가 -1,+1씩 차이가 나는 경우, 해당 좌표로의 위험 지역 분류는 하지 않도록 주의하자.

 

3. 지뢰가 두 칸 옆일 경우, 두 개의 지뢰에게 적용되는 위험 지역의 개수에서 중복되는 공간의 개수를 제거한다.

지뢰의 좌표가 -2,+2씩 차이가 나는 경우, 해당 좌표로의 위험 지역 분류 후 중복되는 좌표는 제거하자.

 

위 경우의 수를 생각해 보았다면, 이제는 어떻게 지뢰와 위험 지역의 좌표를 저장할 것인지에 대해서 고민해야 한다.

위험 지역 좌표를 저장할 배열을 새로 생성하여 저장하는 방법으로 나머지 코드를 작성해보았다.

 

class Solution {
    public int solution(int[][] board) {
        int[][] danger = new int[board.length][board[0].length];
        int bomb = 0;
        int answer = 0;
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                //System.out.println("("+i+","+j+") "+board[i][j]);
                if(board[i][j]==1 & i!=0 & j!=0 & i!=board.length-1 & j!=board[i].length-1){
                    bomb+=1;
                    danger[i][j+1] = 2;
                    danger[i][j-1] = 2;
                    danger[i+1][j] = 2;
                    danger[i-1][j] = 2;
                    danger[i+1][j+1] = 2;
                    danger[i-1][j+1] = 2;
                    danger[i+1][j-1] = 2;
                    danger[i-1][j-1] = 2;
                }else if(board[i][j]==1 & i==0 & j!=0 & i!=board.length-1 & j!=board[i].length-1){
                    bomb+=1;
                    danger[i][j+1] = 2;
                    danger[i][j-1] = 2;
                    danger[i+1][j] = 2;
                    danger[i+1][j+1] = 2;
                    danger[i+1][j-1] = 2;
                }else if(board[i][j]==1 & i!=0 & j==0 & i!=board.length-1 & j!=board[i].length-1){
                    bomb+=1;
                    danger[i][j+1] = 2;
                    danger[i+1][j] = 2;
                    danger[i-1][j] = 2;
                    danger[i+1][j+1] = 2;
                    danger[i-1][j+1] = 2;
                }else if(board[i][j]==1 & i!=0 & j!=0 & i==board.length-1 & j!=board[i].length-1){
                    bomb+=1;
                    danger[i][j+1] = 2;
                    danger[i][j-1] = 2;
                    danger[i-1][j] = 2;
                    danger[i-1][j+1] = 2;
                    danger[i-1][j-1] = 2;
                }else if(board[i][j]==1 & i!=0 & j!=0 & i!=board.length-1 & j==board[i].length-1){
                    bomb+=1;
                    danger[i][j-1] = 2;
                    danger[i+1][j] = 2;
                    danger[i-1][j] = 2;
                    danger[i+1][j-1] = 2;
                    danger[i-1][j-1] = 2;
                }
            }
        }
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                System.out.println("("+i+","+j+") "+danger[i][j]);
                if(danger[i][j]==2) answer+=1;
            }
        }
    
        return board.length*board[0].length - bomb - answer;
    }
}

 

위 코드는 가장자리인 경우에 대해서만 작성한 것이다..

이것만으로도 코드가 너무 길어진다!

하지만 다른 경우도 추가해서 우선 작성해 보자.

 

 

[try2]

class Solution {
    public int solution(int[][] board) {
        int[][] danger = new int[board.length][board[0].length];
        int bomb = 0;
        int answer = 0;
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                //System.out.println("("+i+","+j+") "+board[i][j]);
                if(board[i][j]==1 && i!=0 && j!=0 && i!=board.length-1 && j!=board[i].length-1){
                    if(board[i+1][j]==1 || board[i-1][j]==1 || board[i][j-1]==1 || board[i][j+1]==1) answer-=1;
                    bomb+=1;
                    danger[i][j+1] = 2;
                    danger[i][j-1] = 2;
                    danger[i+1][j] = 2;
                    danger[i-1][j] = 2;
                    danger[i+1][j+1] = 2;
                    danger[i-1][j+1] = 2;
                    danger[i+1][j-1] = 2;
                    danger[i-1][j-1] = 2;
                }else if(board[i][j]==1 && i==0 && j!=0 && i!=board.length-1 && j!=board[i].length-1){
                    if(board[i+1][j]==1 || board[i][j-1]==1 || board[i][j+1]==1) answer-=1;
                    bomb+=1;
                    danger[i][j+1] = 2;
                    danger[i][j-1] = 2;
                    danger[i+1][j] = 2;
                    danger[i+1][j+1] = 2;
                    danger[i+1][j-1] = 2;
                }else if(board[i][j]==1 && i!=0 && j==0 && i!=board.length-1 && j!=board[i].length-1){
                    if(board[i+1][j]==1 || board[i-1][j]==1 || board[i][j+1]==1) answer-=1;
                    bomb+=1;
                    danger[i][j+1] = 2;
                    danger[i+1][j] = 2;
                    danger[i-1][j] = 2;
                    danger[i+1][j+1] = 2;
                    danger[i-1][j+1] = 2;
                }else if(board[i][j]==1 && i!=0 && j!=0 && i==board.length-1 && j!=board[i].length-1){
                    if(board[i-1][j]==1 || board[i][j-1]==1 || board[i][j+1]==1) answer-=1;
                    bomb+=1;
                    danger[i][j+1] = 2;
                    danger[i][j-1] = 2;
                    danger[i-1][j] = 2;
                    danger[i-1][j+1] = 2;
                    danger[i-1][j-1] = 2;
                }else if(board[i][j]==1 && i!=0 && j!=0 && i!=board.length-1 && j==board[i].length-1){
                    if(board[i+1][j]==1 || board[i-1][j]==1 || board[i][j-1]==1) answer-=1;
                    bomb+=1;
                    danger[i][j-1] = 2;
                    danger[i+1][j] = 2;
                    danger[i-1][j] = 2;
                    danger[i+1][j-1] = 2;
                    danger[i-1][j-1] = 2;
                }
                
            }
        }
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                System.out.println("("+i+","+j+") "+danger[i][j]);
                if(danger[i][j]==2) answer+=1;
            }
        }
        System.out.println(bomb);
        return board.length*board[0].length - bomb - answer;
    }
}

 

ㅎㅎ...역시....얼렁뚱땅 넘어갈 리가 없다!

 

 

[try3]

 

사실 어느 부분에서 어떻게 잘못되어가고 있는지 눈으로 잘 확인할 수가 없다..

그래서 중복되는 부분이나 복잡한 부분을 조금 다듬고 진행하기로 했다.

class Solution {
    public int solution(int[][] board) {
        int[][] danger = new int[board.length][board[0].length];
        int bomb = 0; //폭탄의 개수
        int dan = 0; //위험 지역의 개수
        int answer = 0; //안전 지역의 개수
        
        int row_end = board.length-1;
        int col_end = board[0].length-1;
        int total = (row_end+1) * (col_end+1);
        
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                /*폭탄이 1개 또는 2칸 이상 떨어져 있는 경우*/
                if(board[i][j]==1){
                    danger[i][j]=2;
                    /*폭탄이 인접한 경우
                    if (i > 0 && board[i - 1][j] == 1) dan -= 1;
                    if (j > 0 && board[i][j - 1] == 1) dan -= 1;*/
                    /*폭탄이 가장자리인 경우*/
                    if(i==0){ //위쪽 가장자리
                        if(0<j && j<col_end){ //좌우 가장자리 제외
                            danger[i+1][j] = 2; //하
                            danger[i+1][j+1] = 2; //하우
                            danger[i+1][j-1] = 2; //하좌
                            danger[i][j-1] = 2; //좌
                            danger[i][j+1] = 2; //우
                        }else if(j==0){
                            danger[i][j+1] = 2; //우
                            danger[i+1][j] = 2; //하
                            danger[i+1][j+1] = 2; //하우
                        }else if(j==col_end){
                            danger[i][j-1] = 2; //좌
                            danger[i+1][j] = 2; //하
                            danger[i+1][j-1] = 2; //하좌
                        }  
                    }else if(i==row_end){ //아래쪽 가장자리
                        if(0<j && j<col_end){ //좌우 가장자리 제외
                            danger[i-1][j] = 2; //상
                            danger[i-1][j+1] = 2; //상우
                            danger[i-1][j-1] = 2; //상좌
                            danger[i][j-1] = 2; //좌
                            danger[i][j+1] = 2; //우
                        }else if(j==0){
                            danger[i][j+1] = 2; //우
                            danger[i-1][j] = 2; //상
                            danger[i-1][j+1] = 2; //상우
                        }else if(j==col_end){
                            danger[i][j-1] = 2; //좌
                            danger[i-1][j] = 2; //상
                            danger[i-1][j-1] = 2; //상좌
                        }  
                    }/*폭탄이 내부인 경우*/
                    else{
                        if(j==0){
                            danger[i-1][j] = 2; //상
                            danger[i+1][j] = 2; //하
                            danger[i-1][j+1] = 2; //상우
                            danger[i+1][j+1] = 2; //하우
                            danger[i][j+1] = 2; //우
                        }else if(j==col_end){
                            danger[i-1][j] = 2; //상
                            danger[i+1][j] = 2; //하
                            danger[i-1][j-1] = 2; //상좌
                            danger[i+1][j-1] = 2; //하좌
                            danger[i][j-1] = 2; //좌
                        }else{
                            danger[i-1][j] = 2; //상
                            danger[i+1][j] = 2; //하
                            danger[i-1][j+1] = 2; //상우
                            danger[i-1][j-1] = 2; //상좌
                            danger[i][j-1] = 2; //좌
                            danger[i][j+1] = 2; //우
                            danger[i+1][j+1] = 2; //하우
                            danger[i+1][j-1] = 2; //하좌
                        }
                        
                }
                }
                                
            }
        }
        
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                System.out.println("("+i+","+j+") "+danger[i][j]);
                if(danger[i][j]==2) dan+=1;
            }
        }

        return total-dan;
    }
}

 잘 되는 줄 알았는데... 테스트 9에서 런타임에러가 발생했다!

너무 복잡하게 작성한 탓인 것 같았다 😂

반복되는 상하좌우 방향을 설정하는 부분도 없애야 했다!!

 

[try3]

 

class Solution {
    public int solution(int[][] board) {
        int row = board.length;
        int col = board[0].length;

        int[][] danger = new int[board.length][board[0].length];
        int dan = 0; //위험 지역의 개수
    
        
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(board[i][j]==1){
                    danger[i][j]=1;
                    if(i > 0) danger[i-1][j] =1; //상
                    if(i < row-1) danger[i+1][j] =1; //하
                    if(j < col-1) danger[i][j+1] =1; //우
                    if(j > 0) danger[i][j-1] =1; //좌
                    if(i > 0 && j>0) danger[i-1][j-1] =1; //상좌
                    if(i < row-1 && j>0) danger[i+1][j-1] =1; //하좌
                    if(i > 0 && j<col-1) danger[i-1][j+1] =1; //하우
                    if(i < row-1 && j<col-1) danger[i+1][j+1] =1; //상우

                        
                }
                }
                                
            }
        
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(danger[i][j]==1) dan+=1;
            }
        }

        return col*row-dan;
    }
}

 

이전에는 경우의 수를 한줄 한줄 나누어주었다면,

이번에는 범위를 나누어서 전체적으로 적용해주는 방법을 선택했다.

훨씬 간단하게 적을 수 있었는데, 왜 매번 하나부터 열까지 다 경우의 수를 적용하려고 하는지 

이 안좋은 습관이 하루빨리 고쳐지면 좋겠다....😶‍🌫️

---

다른 사람의 풀이 보기

1. 가장자리의 경우의 수를 구하기 번거롭기 때문에 처음부터 위험 지역을 저장할 배열의 크기를 +2씩 늘려서 생성한다. 이렇게 되면 가장자리에서 indexoutofrange error가 발생할 위험을 줄인다.