[프로그래머스] LEVEL2 거리두기 확인하기 (Java)

 

문제

 

분석

사실 이 문제를 굉장히 단순 무식하게 풀었다.

 

대략 문제의 조건을 요약하면

 

1.  중간에 파티션(X)이 존재한다면 거리 두기를 지킨 것이다.

 

2. 파티션을 사이에 두고 앉은 경우도 거리 두기를 지킨것이다. (옆에 빈 테이블이 있으면 안됨)

 

으로 요약 가능하다.

 

생각해보면, 

 

1번 조건은 파티션이 나오면 해당 라인은 더 이상 탐색할 필요가 없는 것이다.

 

2번 조건에서는 P(참가자) 옆에 공석(O)이 있으면 안된다. 

 

라고 해석할 수 있다.

 

이제 알고리즘을 짜보자 

 

탐색을 할 때는 세가지 경우가 있다.

 

1. 파티션(X)이 나오는 경우 

     - 더 이상 볼 필요 없음 skip

 

2. 참가자(P)가 나오는 경우

    - 무조건 안됨

 

3. 공석(O)이 나오는 경우

    - 이건 좀 더 탐색할 필요가 있다.

      주변에 참가자(P) 가 있는 지 확인해 보자

 

이런 메커니즘으로 풀면 문제를 효율적으로 해결할 수 있다.

 

근데 난 상하좌우 대각선 까지 일일이 탐색해주었다 ㅎㅎ...

 

코드

import java.util.*;

class Solution {
    
    static int[] dx = {1,2,-1,-2,0,0,0,0,-1,-1,1,1};
    static int[] dy = {0,0,0,0,1,2,-1,-2,-1,1,-1,1};
    static List<Integer> answer_ = new ArrayList<>();
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for(int i=0;i<5;i++){
            visit(places[i]);
            if(visit(places[i]) == true){
                answer_.add(1);
            }
            else {
                answer_.add(0);
            }
        }
        
        for(int i=0;i<5;i++){
            answer[i] = answer_.get(i);
        }
        
        return answer;
    }
    
    static boolean visit(String[] places){
        for(int j=0;j<5;j++){
                for(int k=0;k<5;k++){
                    if(places[j].charAt(k) == 'P'){
                        check(j,k,places);
                        if(check(j,k,places) == false){
                            return false;
                        }
                    }    
                }
            }    
        return true;
    }
    
    static boolean check(int y,int x,String[] places){
        for(int i=0;i<=7;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) break; 
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X') break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P') return false;
        }
        
        for(int i=2;i<=3;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X') break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P') return false;
        }
        for(int i=4;i<=5;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X') break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P') return false;
        }
        for(int i=6;i<=7;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X') break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P') return false;
        }
        for(int i=8;i<=11;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) continue;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X' || places[y+dy[i]].charAt(x+dx[i]) == 'O') 
                continue;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P'){
                
                
              if(places[y+dy[i]].charAt(x) == 'X' && places[y].charAt(x+dx[i]) == 'X') {
                  continue;
                }
                else return false;
                }
            
            }  
        return true;
        }
        
    
    }