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

#include <string>
#include <vector>

using namespace std;

bool SearchManhattanRange(int aX,int aY, int bX, int bY, const vector<string>& place)
{
    int manhattanRange = abs(aX - bX) + abs(aY - bY);
                
    if (manhattanRange > 2)
    {
        return false;
    }
                
    int minX = min(aX, bX);
    int minY = min(aY, bY);
    
    if (aY == bY)
    {
        if(place[aY][minX + 1] == 'X')
        {
            return false;
        }
    }
    if (aX == bX)
    {
        if (place[minY + 1][aX] == 'X')
        {
            return false;
        }
    }
    if (aX != bX && aY != bY)
    {
        int partition = 0;
        for (int j = minY; j <= minY + 1; ++j)
        {
            for (int k = minX; k <= minX + 1; ++k)
            {
                if (place[j][k] == 'X')
                {
                    partition++;
                }
            }
        }
        
        if(partition == 2)
        {
            return false;
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;

    for (int i = 0; i < places.size(); ++i)
    {
        vector<pair<int, int>> savedP;

        //save person
        for (int j = 0; j < places[i].size(); ++j)
        {
            for (int k = 0; k < places[i][j].size(); ++k)
            {
                if (places[i][j][k] == 'P')
                {
                    savedP.push_back({ k, j });
                }
            }
        }
        
        bool result = true;

        while (!savedP.empty())
        {
            pair<int, int> personA = savedP.back();
            savedP.pop_back();

            for (int j = 0; j < savedP.size(); ++j)
            {
                if(SearchManhattanRange(personA.first, personA.second,
                    savedP[j].first, savedP[j].second, places[i]))
                {
                    result = false;
                    break;
                }
            }
            
            if (!result)
            {
                break;
            }
        }

        if (result)
        {
            answer.push_back(1);
        }
        else
        {
            answer.push_back(0);
        }
    }

    return answer;
}

 

풀이

1. P의 위치들을 저장해준다.

2. P를 하나씩 소거해가며 검사해준다.

3. 맨하튼거리가 2이하인 것만 검사해준다.

4. 가로의 거리가 2일 경우 작은 쪽에서 +1을 하면 사이가 나오므로 해당이 파티션인가 확인

5. 세로도 동일하게 확인

6. 대각선은 서로 x,y좌표가 다를 경우 대각선으로 판단하여 검사

7. 나머지는 거리가 1인것이므로 바로 붙어있음으로 판단

 

 

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

프로그래머스