2021 카카오 채용연계형 인턴십거리두기 확인하기

풀 때 신경쓸 부분은 다음 2가지 정도 인 것 같다.

 

1. 맨하탄 거리

맨하탄 거리는 피타고라스의 정리처럼 직선 거리가 아닌 실제 유효한 이동거리(건물을 뚫고 갈 수 없으니 실제 도보의 길이)임을 기억

 

2. 파티션의 위치

사람 사이에 파티션이 있는지 체크해야 하는데, 직선일 때(X축, Y축)와 대각선으로 있을 때만 구분해서 체크

 

#include <string>
#include <vector>

using namespace std;

// 맨하탄 거리 구하기
int getManhattanDistance(int r1, int c1, int r2, int c2)
{
    return std::abs(r1 - r2) + std::abs(c1 - c2);
}

// 문자열 잘라서 테이블 만들기랑 P의 좌표만 기억해두기
void parse(const vector<string>& place, vector<vector<char>>& table, vector<pair<int, int>>& pos)
{
    table.resize(place.size());

    for (decltype(place.size())i = 0; i < place.size(); ++i)
    {
        table[i].resize(place[i].length());

        for (decltype(place.size())j = 0; j < place.size(); ++j)
        {
            table[i][j] = place[i].at(j);
            if (table[i][j] == 'P')
                pos.push_back(make_pair(i, j));
        }
    }
}

// 주변 파티션 되어있는지 확인
int checkAround(vector<vector<char>>& table, int x1, int y1, int x2, int y2)
{
    if (x1 == x2)
    {
        if ('X' != table[x1][std::min(y1, y2) + 1])
            return 0;
    }
    else if (y1 == y2)
    {
        if ('X' != table[std::min(x1, x2) + 1][y1])
            return 0;
    }
    else
    {
        if ('X' != table[x1][y2] || 'X' != table[x2][y1])
            return 0;
    }
	
    return 1;
}

// 방마다 확인
int check(vector<string>& place) {
    vector<vector<char>> table;
    vector<pair<int, int>> pos;

    parse(place, table, pos);

    for (auto iter = pos.begin(); pos.end() != iter; ++iter)
    {
        for (auto second_iter = iter + 1; pos.end() != second_iter; ++second_iter)
        {
            int manhattan_distance = getManhattanDistance(iter->first, iter->second, second_iter->first, second_iter->second);

            if (1 == manhattan_distance)
                return 0;

            if (2 == manhattan_distance)
            {
                if (0 == checkAround(table, iter->first, iter->second, second_iter->first, second_iter->second))
                    return 0;
            }
        }
    }

    return 1;
}

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

    for (auto& place : places)
        answer.push_back(check(place));

    return answer;
}