[C++] 프로그래머스 거리두기 확인하기 - BFS

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

프로그래머스

풀이

멘하탄 거리가 2이하인 지점에 다른 응시자가 존재한다면, 거리두기 규칙을 지키고 있는지 확인하는 문제이다. 

새로운 P지점마다 BFS를 사용해서 누적 거리가 2 이하인 지점에 대해서 새로운 P가 존재하는지 확인하면 된다. 이때 'X' 영역은 갈 수 없는 영역이다.

한 대기실의 모든 P에 대해 검사를 마쳤고, false가 된 적이 없다면 모두 거리두기를 지키고 있다는 것이므로 answer에 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;
}