[프로그래머스/C++] 거리두기 확인하기

 

프로그래머스

 

 

 

• 모든 응시자가 거리두기 조건을 지키는지 확인해야함
• 조건 1: 응시자 간 맨해튼 거리가 2보다 커야함
• 조건 2: 맨해튼 거리가 2이하더라도 응시자 사이가 파티션으로 막혀 있으면 조건 충족

맨해튼 거리

 

첫 번째 이미지를 보면 조건을 만족하는 경우는

• 맨해튼 거리가 2보다 클 때
• x 좌표가 동일하고 맨해튼 거리가 2지만 중간에 파티션이 존재할 때
• y 좌표가 동일하고 맨해튼 거리가 2지만 중간에 파티션이 존재할 때
• 2x2 영역에서 맨해튼 거리가 2이고 응시자가 앉지 않은 나머지 두 곳 모두 파티션이 존재할 때

이렇게 총 4가지이고, 각 places[i]의 응시자들이 모두 이를 만족하는지 체크하면 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int calcDistance(int x1, int y1, int x2, int y2, vector<string> place) {
    int minX = min(x1, x2);
    int minY = min(y1, y2);
    
    // 맨해튼 거리가 2보다 크면
    if((abs(x1 - x2) + abs(y1 - y2)) > 2) return 1;
    
    // x좌표가 동일하고 맨해튼 거리는 2보다 작으나 중간에 파티션이 존재하면
    if(x1 == x2)
        if(place[x1][minY + 1] == 'X') return 1;
    
    // y좌표가 동일하고 맨해튼 거리는 2보다 작으나 중간에 파티션이 존재하면
    if(y1 == y2)
        if(place[minX + 1][y1] == 'X') return 1;
    
    // x ,y 좌표가 동일하지 않을 때
    if(x1 != x2 && y1 != y2) {
        int partition = 0;
        
        // minX, minY 기준으로 2x2 크기의 정사각형 내에 자리 사이에 파티션이 존재할 때
        for(int i = minX; i <= minX + 1; i++) 
            for(int j = minY; j <= minY + 1; j++)
                if(place[i][j] == 'X') partition++;
        
        // 파티션의 개수가 총 2개면
        if(partition == 2) return 1;
    }
    
    // 모든 조건에 충족되지 않을 때
    return 0;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(int cnt = 0; cnt < 5; cnt++) {
        vector<pair<int, int>> person;
        int result = 1;
        
        // 응시자가 있는 좌표 저장
        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                if(places[cnt][i][j] == 'P') person.push_back({i, j});
        
        // 각 응시자를 기준으로 조건을 충족하는지 체크
        // 충족되지 않는 응시자가 나오면 (result == 0) 반복 중지
        for(int i = 0; i < person.size() && result == 1; i++)
            for(int j = i + 1; j < person.size() && result == 1; j++)
                    result = calcDistance(person[i].first, person[i].second,
                            person[j].first, person[j].second, places[cnt]);
        
        // 결과 삽입
        answer.push_back(result);
    }
    
    return answer;
}