[JAVA] 프로그래머스 - 안전지대

https://school.programmers.co.kr/learn/courses/30/lessons/120866

프로그래머스

 

 

 

 

 

 

 

시도 1)

 

class Solution {
    public int solution(int[][] board) {
        int answer = 0;
        int boardlen = board.length*board.length;
        
        for(int i=0; i<board.length; i++)
        {
            for(int j=0; j<board[i].length; j++)
            {
                if(board[i][j]==1)
                {
                    int row = i; //행
                    int col = j; //열
                    
                    for(int k=Math.max(row-1, 0); k<Math.min(row+2, board.length); k++) {
    for(int l=Math.max(col-1, 0); l<Math.min(col+2, board[i].length); l++) {
        board[k][l] = 1;
    }
}
                }
            }
        }
        
        int count = 0;
        for(int i=0; i<board.length; i++)
        {
            for(int j=0; j<board[i].length; j++)
            {
                if(board[i][j]==1)
                    count++;
            }
        }
        
        answer = boardlen-count;
        return answer;
    }
}

 

 

문제 풀이 

 

[JAVA] 프로그래머스 Lv.0 - 안전지대 — 프로그래밍 고난일지 (tistory.com)

[JAVA] 프로그래머스 Lv.0 - 안전지대

 

 

 

- 순서대로 상,하,좌,우,왼쪽 대각선 위, 왼쪽 대각선 아래, 오른쪽 대각선 위, 오른쪽 대각선 아래를 좌표를 이동할 수 있도록 dir 배열 선언 

 

- board에서 현재 값이 1이라면  지뢰 근처를 탐색하는 find 함수 호출 

 

- dir 배열을 돌면서, 현재 지뢰가 위치한 {row,col}에서 dir 원소의 값을 더하며 좌표를 변경

- 만약 새 좌표가 board 범위에서 벗어나지 않으며, 지뢰가 없는 위치(=0)라면 이 위치에도 접근할 수 없으므로 3으로 업데이트 

 

- 이 과정을 board에 존재하는 모든 지뢰(=1) 좌표를 기준으로 반복

 

 

정답 

 

class Solution {
    public int solution(int[][] board) {
        int answer = 0;
        
        //지뢰 
        int dir[][]= {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,-1},{-1,1},{1,1}};
        
        for(int i=0; i<board.length; i++)
        {
            for(int j=0; j<board[i].length; j++)
            {
                if(board[i][j]==1)
                {
                    find(i,j,dir,board);
                }
            }
        }
        
        for(int i=0; i<board.length; i++)
        {
            for(int j=0; j<board.length; j++)
            {
                if(board[i][j]==0)
                    answer++;
            }
        }
        return answer;
    }
    
    public  void find(int row, int col, int dir[][], int board[][])
    {
        for(int i=0; i<dir.length; i++) {
			//범위 안벗어나게
			if(row+dir[i][0]>=0 && row+dir[i][0]<board.length 
					&& col+dir[i][1]>=0 && col+dir[i][1]<board.length) {
				
				if(board[row+dir[i][0]][col+dir[i][1]]==0) {
                
                //지뢰 주변인 애들
					board[row+dir[i][0]][col+dir[i][1]]=3;
				}
			}
        
        }
    }
}

 

 

 

다른 사람의 풀이 

 

1)

class Solution {

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

    public int solution(int[][] board) {
        int answer = 0;
        int count = 0;

        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board.length; j++) {
                if (board[i][j] == 1) {
                    count++;
                    for (int k=0; k<8; k++) {
                        if (i+dx[k]>=0 && i+dx[k] < board.length && j+dy[k]>=0 && j+dy[k] < board.length && 
                            board[i+dx[k]][j+dy[k]] == 0) {
                            board[i+dx[k]][j+dy[k]] = 2;
                            count++;
                        }
                    }
                }
            }
        }

        answer = board.length * board.length - count;

        return answer;
    }
}

 

 

2)

import java.util.*;

class Solution {

    static int[] dx = { -1, 0, 1, 1, 1, 0, -1, -1 };
    static int[] dy = { -1, -1, -1, 0, 1, 1, 1, 0 };
    static boolean[][] visit;
    static int answer;
    public int solution(int[][] board) {
        answer = 0;

        List<int[]> al = new ArrayList<>(); 
        visit = new boolean[board.length][board.length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board.length; j++){
                if(board[i][j] == 1){
                    al.add(new int[]{i, j});
                    answer++;
                }
            }
        }

        for(int i = 0; i < al.size(); i++){
            int[] tmp = al.get(i);
            dfs(tmp[0], tmp[1], board.length, board);
        }

        return (board.length*board.length) - answer;
    }
    static void dfs(int r, int c, int len, int[][] board){
        visit[r][c] = true;
        for(int i = 0; i < 8; i++){
            int nr = r + dx[i];
            int nc = c + dy[i];
            if(nr < 0 || nc < 0 || nr >= len || nc >= len){
                continue;
            }
            if(!visit[nr][nc] && board[nr][nc] == 0){
                visit[nr][nc] = true;
                board[nr][nc] = 1;
                answer++;
            }
        }
    }
}