[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; }