[JAVA] 2021 카카오 채용연계형 인턴십 【거리두기 확인하기】

---

맨해튼 거리가 사실상, 테이블을 제외한 두 응시자 사이의 격자 거리이므로

 

각 룸마다, 응시자(P)가 발견됐을 때 bfs()를 실행시켜 그 응시자와 가장 가까운 다른 응시자를 찾을때까지 루프문을 돌리고 발견되면 거리를 리턴하도록 bfs()를 구현하였다.

 

가장 가까운 응시자의 거리가 2이하인지 체크한 뒤, 2이하라면 0을 기록하도록 로직을 구성하였다.

---

 

import java.util.*;
class Solution {
    String[][] map;
    boolean[][] checked;
    Queue<int[]> q;
    int[] dr = {1,-1,0,0};
    int[] dc= {0,0,1,-1};
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        Arrays.fill(answer,1);

        for(int i=0;i<places.length;i++){
            setMap(places[i]);

            boolean flag = false;

            for(int j=0;j<5;j++){
                for(int k=0;k<5;k++){
                    if(map[j][k].equals("P")){
                        q = new LinkedList<>();
                        checked = new boolean[5][5];
                        q.offer(new int[]{j,k,0});
                        int result = bfs();
                        if((0<result&&result<=2)){
                            flag = true;
                        }
                    }
                }
            }
            if(flag){
                answer[i]=0;
            }
        }
        return answer;
    }

    int bfs(){
        while(!q.isEmpty()){
            int[] point = q.poll();
            int r=point[0];
            int c=point[1];

            int dist=point[2];
            checked[r][c]=true;

            for(int i=0;i<4;i++){
                int nr = r+dr[i];
                int nc = c+dc[i];
                if(0<=nr && nr<5 && 0<=nc && nc<5 && !checked[nr][nc] && !map[nr][nc].equals("X")){
                    q.offer(new int[]{nr,nc,dist+1});
                    if(map[nr][nc].equals("P")){
                        return dist+1;
                    }
                }
            }
        }
        return -1;

    }

    void setMap(String[] place){
        map = new String[5][5];

        for(int r=0;r<5;r++){

            String[] info = place[r].split("");

            for(int c=0;c<5;c++){
                map[r][c]=info[c];
            }

        }
    }
}