[C++] 프로그래머스 거리두기

https://school.programmers.co.kr/learn/courses/30/lessons/81302#fn1

설명

맨해튼 거리가 2 이하인 지점에 다른 지원자가 있는 경우 거리두기 규정을 준수하고 있는지 확인하는 것이 중요합니다.

각각의 새로운 P 포인트에 대해 BFS를 사용하면 누적 거리가 2 이하인 포인트에 대해 새로운 P가 존재하는지 확인하는 것으로 충분합니다.

이때 “X” 영역은 도달할 수 없는 영역입니다.

모든 P가 대기실에서 테스트되었고 틀린 적이 없다면 거리를 유지하므로 답에 1을, 그렇지 않으면 0을 입력합니다.

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

int dr(4)={0, 1, 0, -1};
int dc(4)={1, 0, -1, 0};
vector<int> answer;

struct Info{
    int row, col, dist;
    Info (int a, int b, int c){
        row=a;
        col=b;
        dist=c;
    }
};

bool bfs(vector<vector<string>>& m, queue<Info> q)
{
    vector<vector<bool>> ch(5, vector<bool> (5, false));
    
    while (!
q.empty()){
        Info v=q.front();
        q.pop();
        
        if (ch(v.row)(v.col) || v.dist==2) continue;
        
        ch(v.row)(v.col)=true;
        for (int i=0; i<4; i++){
            int nr = v.row+dr(i);
            int nc = v.col+dc(i);
            if (nr<0 || nr>4 || nc<0 || nc>4 || m(nr)(nc)=="X") continue;
            int ndist = v.dist+1;
            if (!
ch(nr)(nc)){
                if (m(nr)(nc)=="P") {
                    return false;
                }
                
                q.push(Info(nr, nc, ndist));
            }
        }
    }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    
    for (int i=0; i<places.size(); i++){
        vector<vector<string>> map(5, vector<string> (5, ""));
        vector<pair<int, int>> v;
        for (int j=0; j<places(i).size(); j++){
            for (int k=0; k<places(i)(j).size(); k++){
                map(j)(k) = places(i)(j)(k);
                if (map(j)(k)=="P") v.push_back({j, k}); 

            }
        }
        bool flag=false;
        for (auto i:v){
            queue<Info> q;
            q.push(Info(i.first, i.second, 0));
            if (!
bfs(map, q)){
                flag=true;
                break;
            }
        }
        if (flag) answer.push_back(0);
        else answer.push_back(1);
    }
    return answer;
}