#프로그래머스_거리두기 확인하기 - Java 자바

#유형 : BFS

#난이도 : LV2

# 오랜만에 풀었던 BFS 문제, 동서남북으로 이동하며 조건에 따라 처리하면 된다.

1. 맨해튼거리가 2이하 이면서 응시자가 있다면 false return

2. O(가림막)이면서 맨해튼거리가 2미만이면 큐에 넣어서 탐색을 이어간다.

 

if(places[nextRow].charAt(nextCol) == 'P' && dist <= 2)

     return false;

else if(places[nextRow].charAt(nextCol) == 'O' && dist < 2)

     queue.offer(new Point(nextRow, nextCol));

 

 

import java.util.*;
import java.awt.Point;
 
class Solution {
    static int moveX[] = {-1,0,1,0};
    static int moveY[] = {0,1,0,-1};
    
    
    public static int[] solution(String[][] places) {
            int[] answer = new int[places.length];
            
            for(int i=0; i<places.length; i++) {
                    String tmp[] = places[i];
                    
                    boolean isCheck = true;
                    for(int r=0; r<5 && isCheck; r++) {
                        for(int c=0; c<5 && isCheck; c++) {
                            if(tmp[r].charAt(c) == 'P') {
                                if(!bfs(r,c,tmp))
                                    isCheck = false;
                            }
                        }
                    }
                    answer[i] = isCheck ? 1 : 0;
            }
            
            
            
            return answer;
     }
    
     public static boolean bfs(int r, int c, String []places) {
         Queue<Point> queue = new LinkedList<Point>();
         
         queue.add(new Point(r,c));
         
         while(!queue.isEmpty()) {
             Point p = queue.poll();
             
             for(int d=0; d<4; d++) {
                 int nextRow = p.x + moveY[d];
                 int nextCol = p.y + moveX[d];
                 
                 if(nextCol<0 || nextRow<0 || nextCol>=5 || nextRow>=5 || (nextCol == c && nextRow == r))
                         continue;
                 
                 int dist = Math.abs(nextCol - c) + Math.abs(nextRow - r);
                 
                 if(places[nextRow].charAt(nextCol) == 'P' && dist <= 2)
                     return false;
                 else if(places[nextRow].charAt(nextCol) == 'O' && dist < 2)
                     queue.offer(new Point(nextRow, nextCol));
             }
         }
         
         return true;
     }
     
     
}