프로그래머스 Lv2 거리두기 확인하기 Java

문제설명

https://programmers.co.kr/learn/courses/30/lessons/81302#

구현방법

• 아무것도 모르는 학부생일 때 이 문제 풀고 시간초과 난 적이 있다.
• DFS로 풀었지만 다른사람의 풀이를 보니 그냥 상하좌우 확인하는 것 정도로도 풀린다고 하더라

코드

import java.util.*;
class Solution {
    static char[][] board;
    static boolean[][] visit;
    static int[] mX = {1,0,-1,0};
    static int[] mY = {0,1,0,-1};
    public int[] solution(String[][] places) {
        visit = new boolean[5][5];
        board = new char[5][5];
        int answer[] = new int[5];
        Arrays.fill(answer,1);
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                Arrays.fill(visit[j],false);
                board[j] = places[i][j].toCharArray();
            }
            Loop : for(int m=0;m<5;m++){
                for(int n=0;n<5;n++){
                    if(board[m][n]=='P'){
                        
                        if(dfs(m,n,1)){
                            answer[i] = 1;
                        }
                        else {
                            answer[i]=0;
                            break Loop;
                        }
                    }
                }
            }
        }
        return answer;
    }
    public boolean dfs(int x, int y,int depth){
        boolean ck = true;
        visit[x][y] = true;
        for(int i=0;i<4;i++){
            int tX = x + mX[i];
            int tY = y + mY[i];
            if(check(tX,tY)&&board[tX][tY]=='P'&&!visit[tX][tY]){
                if(depth<=2){ 
                    return false;
                }
            }
            if(check(tX,tY)&&!visit[tX][tY]&&board[tX][tY]=='O'){
                ck = dfs(tX,tY,depth+1);
                if(!ck){
                    return false;
                }
            }
        }
        return true;
    }
    public boolean check(int x, int y){
        if(x<0||x>=5||y<0||y>=5){
            return false;
        }
        return true;
    }
}