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

사람을 발견했을 때

BFS를 통해 탐색을 해서 만약 맨해튼 거리가 2이하인 사람이 있다면 false를 반환해주면 된다. 

이때 만약 탐색 중에 X  즉 파티션을 만나게 되면 파티션 너머는 탐색할 필요가 없어서 continue 처리를 해주면 된다.

그리고 만약 false가 하나라도 있다면 그 대기실은 거리두기를 지키지않는 것이여서 break;처리를 해주면 된다.

#include <string>
#include <vector>
#include <queue>
using namespace std;

int dx[4] = {-1, 1, 0, 0};  // 왼, 오, 아래, 위
int dy[4] = {0, 0, 1, -1};

bool check_dist(int i, int j, vector<string> place) {           //BFS
    bool visited[5][5] = {false};
    queue<pair<pair<int, int>, int>> q;
    visited[i][j] = true;
    q.push({{i, j}, 0});
    
    while (!q.empty()) {
        int cur_x = q.front().first.first;
        int cur_y = q.front().first.second;
        int dist = q.front().second;
        q.pop();
        
        for (int h = 0; h < 4; h++) {
            int nx = cur_x + dx[h];
            int ny = cur_y + dy[h];
            
            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            
            if (visited[nx][ny] || place[nx][ny] == 'X') continue;        //파티션이 있는 경우 너머는 탐색할 필요 없음  
            
            if (place[nx][ny] == 'P' && dist + 1 <= 2) {            //사람이 있는데 맨해튼거리가 지켜지지 않으면
                return false;
            }
            
            visited[nx][ny] = true;
            q.push({{nx, ny}, dist + 1});
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for (auto place : places) {
        bool check = true;
        
        for (int i = 0; i < 5 && check; i++) {
            for (int j = 0; j < 5; j++) {
                if (place[i][j] == 'P') {
                    if (!check_dist(i, j, place)) {
                        check = false;
                        break;
                    }
                }
            }
        }
        
        answer.push_back(check ? 1 : 0);
    }
  
    return answer;
}