(프로그래머스 c++ KAKAO)거리두기 확인하기

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

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

완전 탐색을 실시.

isPossible()함수를 통해 현재 방의 거리두기가 제대로 되어 있는지 확인한다.

directX와 directY는 0번부터 차례대로 1칸씩 상하좌우, 2칸씩 상하좌우, (좌상, 우상, 좌하, 우하) 대각선의 좌표를 구하기 위한 방향 변수다.

 

각 방은 5 x 5이기 때문에 이중 for문으로 빠르게 확인할 수 있다.

현재 위치가 'P'라면 12 방향을 모두 검사하도록 한다.

이중에서 방역 수칙을 제대로 지키지 않았다면 바로 false를 반환하여 answer에 0을 넣어주면 된다.

isPossible()함수의 이중 for문을 모두 통과하게 된다면 방역수칙을 제대로 지켰기 때문에 true가 리턴된다.(answer에 1 추가 가능)

 

state 벡터는 칸막이가 있는 위치를 true로 나타낸다.

이 벡터는 2칸 상하좌우와 대각선을 확인하기 쉽도록 돕는다.

 

#include <string>
#include <vector>
#include <iostream>
#define CHECK(x, y) ((x >= 0 && x < 5 && y >= 0 && y < 5) ? (1) : (0))

using namespace std;

bool isPossible(vector<string> place){
    int directX[12] = {-1, 1, 0, 0, -2, 2, 0, 0, -1, -1, 1, 1};
    int directY[12] = {0, 0, -1, 1, 0, 0, -2, 2, -1, 1, -1, 1};
    vector<vector<bool>> state(5, vector<bool>(5, false));
    
    for(int x = 0; x < 5; x++){
        for(int y = 0; y < 5; y++){
            if(place[x][y] == 'P'){
                for(int k = 0; k < 12; k++){
                    int nx = x + directX[k];
                    int ny = y + directY[k];
                    
                    if(CHECK(nx, ny)){
                        if(k < 4){
                            if(place[nx][ny] == 'P'){
                                return false;
                            }
                            else if(place[nx][ny] == 'X'){
                                state[nx][ny] = true;
                            }
                        }
                        else if(k < 8){
                            if(place[nx][ny] == 'P' && !state[x + directX[k - 4]][y + directY[k - 4]]){
                                return false;
                            }
                        }
                        else{
                            if(place[nx][ny] == 'P'){
                                if(!state[nx][y] || !state[x][ny]){
                                    return false;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(int i = 0; i < places.size(); i++){
        bool isOk = true;
        
        for(int j = 0; j < places[i].size(); j++){
            if(!isPossible(places[i])){
                answer.push_back(0);
                isOk = false;
                break;
            }
        }
        
        if(isOk){
            answer.push_back(1);
        }
    }
    return answer;
}