[프로그래머스 *Java] - 거리두기 확인하기

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

프로그래머스

조건

제한시간 : 45분 이내

 

시간 내에 풀지 못했음.
로직 설계를 할 때, 너무 복잡하게 했던 부분도 있고
설계를 하는 도중에 10분이 넘어가니깐 마음이 급해져서 설계가 마무리되지 않은 상태에서 바로 구현에 들어갔음.
그러니, 완벽하지 않은 로직과 input Data 타입도 착각하고 코드를 구현해서 '맞왜틀' 하다가 시간이 끝남.

bfs 를 간만에 풀어서 그런지, 머리가 굳었던 거 같음.

 

import java.util.*;
 
class Solution {
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0 ,-1};
    final int side = 5;
    
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        for(int i = 0; i < places.length; i++){
            answer[i] = searchP(places[i]);
        }
        
        return answer;
    }
    
    public int searchP(String[] board) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length(); j++){
                if(board[i].charAt(j) == 'P') { 
                    if(!bfs(board, i, j)) return 0; 
                }
            }
        }
        return 1;
    }
    
    public boolean isRange(int x, int y) {
        if(x < 0 || y < 0 || x >= side || y >= side) return false;
        return true;
    }
    
    public boolean bfs(String[] board, int x, int y) {
        Queue<Node> qu = new LinkedList<>();
        boolean[][] visited = new boolean[side][side];
        qu.offer(new Node(x, y));
        visited[x][y] = true;
        
        while(!qu.isEmpty()) {
            Node current = qu.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                
                int manhattan = Math.abs(x - nx) + Math.abs(y - ny);
                
                if(!isRange(nx, ny)) continue;
                if(visited[nx][ny] || manhattan > 2) continue;
                
                char newV = board[nx].charAt(ny);
                if(newV == 'X' ) continue;                
                else if(newV == 'P') return false;
                
                visited[nx][ny] = true;
                qu.offer(new Node(nx, ny));
            }
        }
        return true;
    }
    
    public class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}