프로그래머스 거리두기 확인하기 [Lv. 2] (C++)

프로그래머스

대기실의 모습을 입력받을 때, 거리두기를 잘 지키고 있는지 체크해주세요.

 

거리두기 조건

1. 사람과 사람 사이의 거리는 3 이상 (대각선은 2로 판단)

2. 거리가 2이하일 경우 사이에 파티션이 있다면 거리두기를 잘 지키고 있다고 판단

 

 

 

풀이 방법

모든 사람의 위치값을 비교하는 방식으로 거리두기를 지키고 있는지 체크해야합니다.

int dist = abs(cy - ty) + abs(cx - tx);
if (dist == 1)
    return false;

비교하는 사람 사이의 거리가 1이라면 해당 대기실은 거리두기를 지키고 있지 않다고 판단합니다.

 

if (dist == 2)
{
    if (cy == ty && cx != tx && places[cy][(cx+tx)/2] != 'X')
        return false;
    if (cx == tx && cy != ty && places[(cy+ty)/2][cx] != 'X')
        return false;
    if (cy != ty && cx != tx)
    {
        if (places[cy][tx] != 'X' || places[ty][cx] != 'X')
            return false; 
    }
}

비교하는 사람 사이의 거리가 2일 때는 3개의 경우가 있습니다.

X축으로 2만큼 떨어져 있는 경우, Y축으로 2만큼 떨어져 있는 경우, X축, Y축으로 1만큼씩 떨어져 있는경우입니다.

어떤 경우인지 찾고 그 사이에 파티션이 위치해 있는지 찾습니다.

파티션이 없다면 거리두기를 지키지 않는 대기실로 판단합니다.

 

 

정답 코드

#include <string>
#include <vector>

using namespace std;

bool CHECK(vector<string>& places, vector<pair<int, int>>& P)
{
    for (int i = 0; i < P.size(); i++)
    {
        for (int j = i+1; j < P.size(); j++)
        {
            auto& [cy, cx] = P[i];
            auto& [ty, tx] = P[j];

            int dist = abs(cy - ty) + abs(cx - tx);
            if (dist == 1)
                return false;
            
            if (dist == 2)
            {
                if (cy == ty && cx != tx && places[cy][(cx+tx)/2] != 'X')
                    return false;
                if (cx == tx && cy != ty && places[(cy+ty)/2][cx] != 'X')
                    return false;
                if (cy != ty && cx != tx)
                {
                    if (places[cy][tx] != 'X' || places[ty][cx] != 'X')
                        return false; 
                }
            }
        }
    }
    return true;
}
    
vector<int> solution(vector<vector<string>> places) {
    vector<int> answer(places.size());
    
    vector<vector<pair<int, int>>> PPos(places.size(), vector<pair<int, int>>());
    for (int k = 0; k < places.size(); k++)
    {
        auto& place = places[k];
        for (int i = 0; i < place.size(); i++)
            for (int j = 0; j < place[i].size(); j++)
                if (place[i][j] == 'P')
                    PPos[k].push_back({i, j});
    }
    
    for (int i = 0; i < PPos.size(); i++)
        answer[i] = CHECK(places[i], PPos[i]) ? 1 : 0;

    
    return answer;
}