[자바] 거리두기 확인하기

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

프로그래머스

풀수있었을것같은데, 헤맨문제.

BFS.DFS를 다시 공부하자..! 

 

P가 나오면, 문자열 배열에서 그 주변으로 거리가 2인 범위 내에 P가 X없이 있는지를 보는 문제이다.

P주변으로 4방탐색을 해야하는데, 거리가 2범위 내이어야하기 때문에 queue에 넣고 bfs를 도는 문제이다.

주변에 d<=2이고, P가 있으면 false이고, d<2이고 O가 있으면 탐색가능한지역이기 때문에 queue에 넣고 돌린다.

 

ans변수로 false, true여부를 체크해줬다. 

import java.util.*;
class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for (int i=0; i<5; i++) {
            String[] temp = places[i]; //문자열 * 5개
            boolean ans = true;
            
            for (int j=0; j<5 && ans; j++) {
                for (int k=0; k<5 && ans; k++) {
                    if(temp[j].charAt(k)=='P') {
                        if (!bfs(j,k,temp)) {
                            ans=false;
                        }
                    }
                }
            }
            if (ans) {answer[i]=1;}
        }
        return answer;
    }
    
    public static boolean bfs(int r, int c, String[] st) {
        int[] dx = new int[] {-1,0,1,0};
        int[] dy = new int[] {0,-1,0,1};
        
        Queue<int[]> q = new LinkedList<int[]>();
        q.offer(new int[] {r,c});
        
        while (!q.isEmpty()) {
            int[] rc=q.poll();
            int x = rc[0];
            int y=rc[1];
            for (int i=0; i<4; i++) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                if (nx<0 || nx>=5 || ny<0 || ny>=5 ||(nx == r && ny == c)) {
                    continue;
                }
                int d = Math.abs(nx-r)+Math.abs(ny-c);
                
                if(d<=2 && st[nx].charAt(ny)=='P') {
                    //사람이 있으면
                    return false; 
                }
                else if (d<2 && st[nx].charAt(ny)=='O') {
                    q.add(new int[] {nx,ny});
                }
            }
        }
        return true;
        
    }
}