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

프로그래머스의 거리두기 확인하기 (Lv2) 문제이다.

 

[ 문제풀이 ]

시험에 응시하는 응시자들 간의 거리가 2이하가 되도록 앉아 있는지 확인하는 문제이다.

 

#1. 맨해튼 거리 '2' 이하

문제에서 응시자들의 간의 거리는 '맨해튼 거리 2이하' 가 되면 안된다고 주어져있다.

이 거리는 (x , y)와 (xx , yy)가 있을 때, |x - xx| + |y - yy| <= 2 라는 것을 의미한다.

이 거리는, BFS 혹은 DFS같은 방식으로 탐색을 진행했을 때 깊이가 '2'이하인 지점들을 의미한다.

따라서, 본인은 이 문제를 BFS탐색을 이용해서 접근해 보았다.

 

#2. BFS 탐색 과정

어느 한 응시자로부터 탐색을 시작한다고 가정해보자.

우리는 탐색하는 과정에서 다음과 같은 3가지 상황을 만나게 될 것이다.

1. 'P' 사람을 만나는 경우

탐색 과정 중에, 사람을 만나는 경우가 발생한다면 지금 우리가 시작 좌표로부터 몇 칸을 움직였는지를 확인을 해봐야 한다. 만약, 3칸 이상을 움직였는데 사람을 만난다면 문제가 되지 않을 것이다.

하지만, 2칸 이하로 움직였는데 사람을 만나게 된다면 이는 맨해튼 거리 2 이하를 지키지 않고 있는 것이므로 거리두기를 지키고 있지 않는 것이 될 것이다.

하지만 ! 본인은 사람을 만나게 되면 움직인 거리에 상관없이 무조건 거리두기를 지키지 않는다고 판단해 주었다.

왜냐하면 본인은 탐색을 진행할 때, 깊이를 2인 지점까지만 탐색을 했기 때문이다.

즉 ! 깊이가 2가 되는 순간 그 이후에는 탐색을 진행하지 않았다. 그렇기 때문에, 본인이 구현한 코드에 의하면, 탐색 과정 사람을 만나게 되면 이는 무조건 깊이가 2이하인 상태에서 사람을 만난 것이 되고 거리두기를 지키지 않은 것이 되는 것이다.

2. 'X' 파티션을 만나는 경우

파티션을 만나게 된다면, 이는 탐색을 할 필요가 없다. 즉 ! "탐색할 수 없는 지점" 이라고 생각을 하면 된다.

그렇기 때문에 본인은 파티션을 만나는 경우에 대해서는 탐색을 진행하지 않았다.

3. 'O' 빈 테이블을 만나는 경우

이 경우에는 탐색을 진행해 주었다. 움직인 거리를 늘려가면서 탐색을 하는 유일한 좌표라고 볼 수 있다.

 

이 모든 과정을 코드로 나타내면 다음과 같다.

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

bool BFS(int a, int b, vector<string> MAP)
{
	vector<vector<bool>> Visit(5, vector<bool>(5, false));
	queue<pair<pair<int, int>, int>> Q;
	Q.push(make_pair(make_pair(a, b), 0));
	Visit[a][b] = true;

	while (Q.empty() == 0)
	{
		int x = Q.front().first.first;
		int y = Q.front().first.second;
		int Cnt = Q.front().second;
		Q.pop();

		if (Cnt == 2) continue;

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5)
			{
				if (Visit[nx][ny] == false)
				{
					if (MAP[nx][ny] == 'O')
					{
						Visit[nx][ny] = true;
						Q.push(make_pair(make_pair(nx, ny), Cnt + 1));

					}
					else if (MAP[nx][ny] == 'P')
					{
						return false;
					}
				}
				
			}
		}
	}
	return true;
}

line18)에서 보면, 깊이가 2가 되는 순간 더 이상의 탐색은 하지 않는다는 것을 구현해 주었다.

실제 탐색을 진행할 때에는, 빈 테이블을 만났을 때만 탐색을 진행하고, 파티션을 만났을 때는 탐색을 하지 않을 것이기 때문에 구현조차 하지 않았다.

그리고, 사람을 만나는 경우에는 무조건 맨해튼 거리가 2이하인 지점에서 사람을 만났다는 것을 의미하므로 거리두기를 지키지 않는다 판단하고 바로 false를 return 해 주었다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
bool BFS(int a, int b, vector<string> MAP)
{
    vector<vector<bool>> Visit(5, vector<bool>(5, false));
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(a, b), 0));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Cnt == 2) continue;
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5)
            {
                if (Visit[nx][ny] == false)
                {
                    if (MAP[nx][ny] == 'O')
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
 
                    }
                    else if (MAP[nx][ny] == 'P')
                    {
                        return false;
                    }
                }
                
            }
        }
    }
    return true;
}
 
int Find_Answer(vector<string> MAP)
{
    for (int i = 0; i < MAP.size(); i++)
    {
        for (int j = 0; j < MAP[i].size(); j++)
        {
            if (MAP[i][j] == 'P')
            {
                if (BFS(i, j, MAP) == false)
                {
                    return 0;
                }
            }
        }
    }
    return 1;
}
 
vector<int> Function(vector<vector<string>> MAP)
{
    vector<int> Result;
    for (int i = 0; i < MAP.size(); i++)
    {
        Result.push_back(Find_Answer(MAP[i]));
    }
    return Result;
}
 
vector<int> solution(vector<vector<string>> places)
{
    vector<int> answer;
    answer = Function(places);
    return answer;
}