[C++]2021 카카오 채용연계형 인턴십 거리두기 확인하기(프로그래머스 2레벨)

#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
int visit[5][5] = {};
 
bool bfs(int iX, int iY, vector<string> vecString) 
{
    queue <pair<int, int>> que;
    que.push({ iX,iY });
    visit[iX][iY] = 1;
 
    while (!que.empty()) 
    {
        // 큐에 있는 맨 위를 뺀 후 입력한다.
        int iFirstX = que.front().first;
        int iSecondY = que.front().second;
        que.pop();
 
        for (int i = 0; i < 4; ++i) 
        {
            // 네 방향으로 큐를 더 입력
            int iNextX = iFirstX;
            int iNextY = iSecondY;
 
            if (i == 0)
                ++iNextX;
            else if (i == 1)
                ++iNextY;
            else if (i == 2)
                --iNextX;
            else
                --iNextY;
 
            // 범위에서 넘어가면 다음으로
            if (0 > iNextX || iNextX >= 5 || 0 > iNextY || iNextY >= 5)
                continue;
 
            // 방문했거나 파티션으로 막혀있다면 통과니까 다음으로
            if (vecString[iNextX][iNextY] == 'X' || visit[iNextX][iNextY])
                continue;
 
            // 이전 방문할 곳보다 1크게 해서 입력
            visit[iNextX][iNextY] = visit[iFirstX][iSecondY] + 1;
 
            // P를 찾았고, 그 곳의 방문이 3번째 보다 낮으면 0을 리턴
            if (vecString[iNextX][iNextY] == 'P')
                if (visit[iNextX][iNextY] <= 3)
                        return false;
 
            // 아니라면 큐에 다시 입력
            que.push({ iNextX,iNextY });
        }
    }
 
    return true;
}
 
vector<int> solution(vector<vector<string>> places)
{
    vector<int> answer;
 
    for (int i = 0; i < places.size(); i++) 
    {
        bool bSucc = true;
 
        for (int j = 0; j < places[i].size(); j++) 
        {
            for (int z = 0; z < places[i][j].size(); z++) 
            {
                // 시작하기 전에 visit을 0으로 초기화
                memset(visit, 0, sizeof(visit));
 
                if (places[i][j][z] == 'P' && !visit[j][z]) 
                {
                    bSucc = bfs(j, z, places[i]);
 
                    // 실패했다면 아예 끝까지 뺀 후에 answer에 입력 후 다시 시작
                    if (!bSucc)
                        break;
                }
            }
 
            if (!bSucc)
                break;
        }
 
        if (!bSucc)
            answer.push_back(0);
 
        else 
            answer.push_back(1);
    }
 
    return answer;
}

파티션의 역할을 좀 생각해봐야 할 필요가 있다.

파티션이 있다면 어떻게든 거리는 2이상일 것이고 파티션으로 인해서 거리두기는 성공이기 때문에 빼도 될 것이다.