[2021 카카오 인턴십 코딩테스트/c++] 거리두기 확인하기

다 풀고 나니까 쉬운 문제였는데.. 말도 안 되게 계속 헤매가지고 오래 걸렸다 😕

 

✨ 문제 풀이

내가 생각했을 때 이 문제를 풀기 위해서 가장 중요한 부분은 다음과 같았다.

 

1. 맨해튼 거리 2 이하 내에 두 사람이 위치해 있으면 X

2. 두 사람 사이에 파티션이 존재하면 괜찮음

 

먼저 맨해튼 거리 2 이하라는 조건을 생각해보았다. 일직선 상에 2칸 이내와 대각선으로 한 칸 이내는 모두 맨해튼 거리 2 이하이다.

그리고 두 번째 조건에 대해 생각해보았다. 일직선 상에 있을 때는 두 사람 사이에 파티션이 존재하는 걸 쉽게 생각할 수 있지만, 대각선 상에 있을 때는 어떻게 파티션이 존재해야 하는지 생각해야 한다.

 

한 칸 대각선 위에 있는 사람과 거리두기를 만족하려면 두 사람을 이을 수 있는 동서남북 방향이 모두 막혀있어야 한다. 이걸 잘 생각해보면 동서남북 방향으로 움직일 수 있다고 할 때 ㄱ, ㄴ자로 2칸 움직이는 데 파티션이 없어서 자유롭다면 거리두기를 만족하지 못한다는 것이다. 설명하기 쉽게 그림으로 표현하자면,

 

이런 접근이 가능하면 거리두기를 지키지 못했다는 것이다.

이 부분을 잘 이용해주니까 맨해튼 거리를 별도 계산해주는 식을 만들지 않고도 BFS로 문제 해결이 가능했다.

 

내가 문제를 해결한 방법은 다음과 같다.

 

1. 5x5 대기실에서 사람이 앉아있는 (P) 부분들을 모두 탐색한다.

2. ((y좌표, x좌표), 이동 칸 수)를 queue에 저장하면서 탐색한다.

3. 이동 칸 수가 0보다 크고 2 이하인데, 만약 사람이 앉아 있다면 false 반환

3. 이동 칸 수가 2보다 큰데 사람이 앉아있다면, 이 사람을 기준으로 다시 다른 사람과의 거리를 계산해야 하므로 이동 칸 수 0으로 수정

4. 파티션을 만나면 아예 이동하지 않음

 

BFS를 이용해서 탐색을 진행했다.

 

🗓 코드

#include <string>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

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

bool visited[5][5];

void init()
{
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            visited[i][j] = false;
}

bool checkPartition(vector<string> map, int cy, int cx)
{
    queue<pair<pair<int, int>, int>> q;
    q.push({{cy, cx}, 0});
    while (!q.empty())
    {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int count = q.front().second;
        q.pop();

        // printf("(%d, %d) : %d [%c]\n", y, x, count, map[y][x]);
        if (map[y][x] == 'P' && count <= 2 && count > 0)
            return false;
        if (map[y][x] == 'P')
            count = 0;

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5)
                continue;
            if (map[ny][nx] == 'X')
                continue;
            if (!visited[ny][nx])
            {
                visited[ny][nx] = true;
                q.push({{ny, nx}, count + 1});
            }
        }
    }
    return true;
}

vector<int> solution(vector<vector<string>> places)
{
    vector<int> answer;
    // 1. 한 대기실 별로 확인한다.
    // 2. 만약 P라면 BFS 확인
    // 3. 2 이하만큼 이동한 후에 (X가 있으면 이동 못함) P가 나오면 0
    // 4. 5x5 대기실을 모두 확인해도 거리두기를 위반한 사람이 없으면 1
    for (vector<string> place : places)
    {
        init();
        bool flag = true;
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                if (!visited[i][j] && place[i][j] == 'P')
                {
                    visited[i][j] = true;
                    flag = checkPartition(place, i, j);
                }
                if (!flag)
                    break;
            }
            if (!flag)
                break;
        }
        if (!flag)
            answer.push_back(0);
        else
            answer.push_back(1);
    }
    return answer;
}