Level 2. 거리두기 확인하기

Level 2. 거리두기 확인하기

 

 

하나의 자리에 대해 마름모 모양으로 주변 12가지 자리에 대해 검사하면 되므로, 그냥 모든 경우를 구현했다.

 

#include <iostream>
#include <vector>

using namespace std;

bool check_distancing(vector<string>& place, int i, int j)
{
    int row = place.size();
    int col = place.front().length();

    auto check_bound = [row, col](int i, int j) { return (0 <= i) && (i < row) && (0 <= j) && (j < col); };

    if (check_bound(i - 1, j))
    {
        if (place[i - 1][j] == 'P') return false;

        if (place[i - 1][j] == 'O')
        {
            if (check_bound(i - 1, j - 1) && place[i - 1][j - 1] == 'P') return false;
            if (check_bound(i - 1, j + 1) && place[i - 1][j + 1] == 'P') return false;
            if (check_bound(i - 2, j)     && place[i - 2][j] == 'P')     return false;
        }
    }

    if (check_bound(i + 1, j))
    {
        if (place[i + 1][j] == 'P') return false;

        if (place[i + 1][j] == 'O')
        {
            if (check_bound(i + 1, j - 1) && place[i + 1][j - 1] == 'P') return false;
            if (check_bound(i + 1, j + 1) && place[i + 1][j + 1] == 'P') return false;
            if (check_bound(i + 2, j)     && place[i + 2][j] == 'P')     return false;
        }
    }

    if (check_bound(i, j - 1))
    {
        if (place[i][j - 1] == 'P') return false;

        if (place[i][j - 1] == 'O')
        {
            if (check_bound(i - 1, j - 1) && place[i - 1][j - 1] == 'P') return false;
            if (check_bound(i + 1, j - 1) && place[i + 1][j - 1] == 'P') return false;
            if (check_bound(i, j - 2)     && place[i][j - 2] == 'P')     return false;
        }
    }

    if (check_bound(i, j + 1))
    {
        if (place[i][j + 1] == 'P') return false;

        if (place[i][j + 1] == 'O')
        {
            if (check_bound(i - 1, j + 1) && place[i - 1][j + 1] == 'P') return false;
            if (check_bound(i + 1, j + 1) && place[i + 1][j + 1] == 'P') return false;
            if (check_bound(i, j + 2)     && place[i][j + 2] == 'P')     return false;
        }
    }

    return true;
}

bool check_place(vector<string>& place)
{
    for (int i = 0; i < place.size(); ++i)
        for (int j = 0; j < place[i].length(); ++j)
            if (place[i][j] == 'P' && check_distancing(place, i, j) == false)
                return false;

    return true;
}

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

    for (vector<string>& place : places)
        answer.emplace_back(check_place(place));

    return answer;
}

 

내 방법보다는 좀 더 깔끔한 방법이다.

 

맨해튼 거리가 2인 자리들은 즉시 확인하는 것이 아니라, 표시만 해뒀다가 나중에 다른 사람이 확인하도록 하는 방법이다.

 

또, 음수 범위 검사를 자료형을 unsigned로 지정해 처리한 것이 인상적이다.

 

#include <iostream>
#include <vector>

using namespace std;

bool check_place(vector<string>& place)
{
    int row = place.size();
    int col = place.front().length();
    vector<vector<int>> isInUse(row, vector<int>(col, false));

    int dx[] = {1, -1,  0,  0};
    int dy[] = {0,  0,  1, -1};

    for (int x = 0; x < row; ++x)
    {
        for (int y = 0; y < col; ++y)
        {
            if (place[x][y] == 'P')
            {
                for (int z = 0; z < 4; ++z)
                {
                    unsigned moved_x = x + dx[z];
                    unsigned moved_y = y + dy[z];

                    if (row <= moved_x || col <= moved_y)
                        continue;

                    switch (place[moved_x][moved_y])
                    {
                    case 'P':
                        return false;
                    case 'O':
                        if (isInUse[moved_x][moved_y])
                            return false;
                        else
                            isInUse[moved_x][moved_y] = true;
                        break;
                    default:
                        break;
                    }
                }
            }
        }
    }

    return true;
}

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

    for (vector<string>& place : places)
        answer.emplace_back(check_place(place));

    return answer;
}