[프로그래머스] LV 2 거리두기 확인하기

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

프로그래머스

 

접근 방법

1. 탐색 범위가 5*5*5 이므로 맘편히 완탐하면된다.
2. 구현 단계도 굉장히 심플하다 
   1. 각 격자 탐색
   2. 체크 및 배열 저장
   3. 배열 반환
3. 체크 구현
   1. 먼저 맨해튼 거리 2 이하인 위치를 사전에 정해놓았다 (checkLoc)
   2. 전체 격자를 순회하며 !OOB이고 checkLoc 배열로 움직인 r2,c2 또한 P일때 검사를 수행한다
   3. 거리가 1이하면 거리 두지 않았다
   4. 2이상일때, 사람 사이 경로가 모두 파티션이어야한다

[구현시 놓쳤던 것]

• 왼쪽 아래 위치를 빼먹고 5개의 위치만 검사했다
• existPartition()에서 sr,sc,er,ec로 변환하지 않고 구현했다

코드

class Solution {
    int n = 5;
    int[][] checkLoc = {{1,0},{2,0},{0,1},{0,2},{1,1},{1,-1}};
    public int[] solution(String[][] places) {
        int[] ans = new int[n];
        for(int i = 0 ; i < n ; i++){
            ans[i] = check(places[i]);
        }
        return ans;
    }
    int check(String[] place){
        for(int i = 0 ; i < n*n ; i++){
            int r1 = i / n;
            int c1 = i % n;
            if(place[r1].charAt(c1) != 'P') continue;
            
            for(int j = 0 ; j < 6 ; j++){
                int r2 = r1+checkLoc[j][0];
                int c2 = c1+checkLoc[j][1];
                
                if(OOB(r2,c2) || place[r2].charAt(c2) != 'P') continue;
                
                if(getDist(r1,c1,r2,c2) == 1) return 0;
                
                if(existPartition(r1,c1,r2,c2, place)) continue;
                return 0;
            }
        }
        return 1;
    }
    int getDist (int r1,int c1,int r2,int c2){
        return Math.abs(r1-r2) + Math.abs(c1-c2);
    }
    boolean existPartition(int r1,int c1,int r2,int c2, String[] place){
        int sr = Math.min(r1,r2);
        int er = Math.max(r1,r2);
        int sc = Math.min(c1,c2);
        int ec = Math.max(c1,c2);
        
        for(int i = sr ; i <= er ; i++){
            for(int j = sc ; j <= ec ; j++){
                if((i == r1 && j == c1 )|| (i == r2 && j == c2)) continue;

                if(place[i].charAt(j) != 'X') return false;
            }
        }
        return true;
    }
    boolean OOB(int r,int c){
        return r < 0 || r >= n || c < 0 || c >= n;
    }
}