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

 구현 문제이다. 

 각 방의 모든 사람의 위치를 구하고, 모든 사람들의 서로 간의 거리를 확인하자.

 문제 조건대로 거리가 1이면 거리 두기 위반, 2이면 위반했는지 확인 필요, 3 이상이면 거리 두기이다.

 핵심은 거리가 2일 때 위반했는지 확인하는 것인데, 거리가 2인데 거리 두기를 유지하는 경우는 

1. P X P
2. P
   X
   P
3. P X
   X P
4. X P
   P X

 이렇게 4가지 경우 밖에 없다. 이것만 잘 확인해주면 쉽게 풀리는 문제다.

 

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <math.h>

using namespace std;

char room[5][5][5];
vector<pair<int, int>> person[5];
bool checkPartition(int, pair<int, int>&, pair<int, int>&);

// 거리 계산
int calDist(pair<int, int>& p1, pair<int, int>& p2) {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

// 각 대기실에 있는 사람들간의 거리 확인
bool checkDist(int cur) {
    if (person[cur].size() == 0) return true;
	// 지금 생각해보니 sorting이 필요없다.. 이미 sort되어있는 상태이기 때문
    sort(person[cur].begin(), person[cur].end());

    for (int i = 0; i < person[cur].size(); ++i) {
        for (int j = i + 1; j < person[cur].size(); ++j) {
            int dist = calDist(person[cur][i], person[cur][j]);
            // 거리가 1이면 거리두기 위반
            if (dist == 1) return false;
            // 거리가 2이면 거리두기 위반했는지 확인
            else if (dist == 2) {
                if (!checkPartition(cur, person[cur][i], person[cur][j]))
                    return false;
            }
        }
    }
    // 이중 for문을 빠져나왔다면 거리두기를 지킨 것이다.
    return true;
}

bool checkPartition(int cur_room, pair<int, int>& p1, pair<int, int>& p2) {
    // P X P
    if (p1.first == p2.first) {
        if (room[cur_room][p1.first][p1.second + 1] == 'X') return true;
    }
    // P
    // X
    // P
    else if (p1.second == p2.second) {
        if (room[cur_room][p1.first + 1][p1.second] == 'X') return true;
    }
    else {
        // P X 
        // X P  
        if (p1.second < p2.second) {
            if (room[cur_room][p1.first][p1.second + 1] == 'X'
                &&
                room[cur_room][p2.first][p2.second - 1] == 'X'
                )
                return true;
        }
        // X P
        // P X
        else {
            if (room[cur_room][p1.first][p1.second - 1] == 'X'
                &&
                room[cur_room][p2.first][p2.second + 1] == 'X'
                )
                return true;
        }
    }

    return false;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            for (int k = 0; k < 5; ++k) {
                room[i][j][k] = places[i][j][k];
                if (room[i][j][k] == 'P') person[i].push_back({ j, k });
            }
        }
    }
    for (int i = 0; i < 5; ++i) {
        if (checkDist(i)) answer.push_back(1);
        else answer.push_back(0);
    }

    return answer;
}