거리두기 확인하기

문제 조건

 

5X5 행렬

 

1. 거리두기 가능 조건

1-1. 맨허튼 거리(좌표 절대값 거리) > 2 

1-2. 파티션은 막혀있다.

-> BFS || DFS로 탐색을 하면 되겠다.

-> 탐색을 할 때, 거리가 2 이상인 것은 조회할 필요가 없다.

 

2. 거리두기

-> 거리두기가 false인 상황에는 조회 할 필요가 없다.

 

문제 풀이

1. String 배열을 split("")를 이용하여 이차원 배열을 만듬

2. 체크를 위한 visit[][] 선언 및 초기화

3. 이차원 배열을 만들면서 ArrayList에 "P"의 x,y좌표와 cnt를 0으로 넣어준다.

4. P를 기준으로 BFS 탐색

4-1. 거리가 2 초과시 탐색 무시(continue)

4-2. 거리가 2 미만인데 "P"를 만날 경우 탐색 종료 (return false)

 

 

**네이밍 연습

**방향을 탐색으로 잡았는데 탐색을 안하고도 방법이 있을 꺼 같은 느낌

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[] dx = {-1,0,1,0};
    public int[] dy = {0,1,0,-1};

    class human{
        int x;
        int y;
        int cnt;
        public human(int x, int y, int cnt){
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    public boolean sol(String[] room){
        String[][] map = new String[5][5];
        boolean[][] visit = new boolean[5][5];
        ArrayList<human> h = new ArrayList<human>();

        for(int i=0; i<room.length; i++){
            String[] temp = room[i].split("");
            for(int j=0; j<temp.length; j++){
                map[i][j] = temp[j];
                visit[i][j] = false;
                if(temp[j].equals("P")){
                    h.add(new human(i,j,0));
                }
                
            }
        }
        
        for(int i=0; i<h.size(); i++){

            Queue<human> q = new LinkedList<>();
            q.add(h.get(i));
            while(!q.isEmpty()){
                human temp = q.poll();
                int hx = temp.x;
                int hy = temp.y;
                int hCnt = temp.cnt;
                visit[hx][hy] = true;
                if(hCnt > 2){
                    break;
                }
                for(int k=0; k<4; k++){
                    int xx = hx + dx[k];
                    int yy = hy + dy[k];
                    if(xx <0 || yy<0|| xx>4||yy>4){
                        continue;
                    }
                    if(visit[xx][yy] == false && map[xx][yy] != "X"){
                        if(map[xx][yy].equals("P") && hCnt < 2){
                            return false;
                        }
                        if(map[xx][yy].equals("O")){
                            int t = hCnt +1;
                            q.add(new human(xx, yy, t));
                        }
                    }

                }
            }

            for(int idx=0; idx<5; idx++){
                for(int j=0; j<5; j++){
                    visit[idx][j] = false;
                }
            }


        }
        return true;
    }
    
    
    public int[] solution(String[][] places) {
       int[] answer = new int[5];
        for(int i=0; i<places.length; i++){
            if(sol(places[i])){
                answer[i] = 1;
            } else{
                answer[i] = 0;
            }
        }

        return answer;
    }
}

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

코딩테스트 연습 - 거리두기 확인하기