[Programmers] 거리두기 확인하기 (C++)

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

코딩테스트 연습 - 거리두기 확인하기

 

#include <string>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };
int dist[6][6];

void bfs(int a, int b, int i, const vector<vector<string>> places){
    queue<pair<int, int>> q;
    q.push({a, b});
    dist[a][b] = 0;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int k = 0; k < 4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];

            if(!(nx >= 0 && nx < 5 && ny >= 0 && ny < 5)) continue;

            if(dist[nx][ny] == -1 && places[i][nx][ny] != 'X'){
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;

    for(int i = 0; i < 5; i++){
        bool flag = true;

        for(int a = 0; a < 5; a++){
            for(int b = 0; b < 5; b++){
                char now = places[i][a][b];

                if(now != 'P') continue;

                memset(dist, -1, sizeof(dist));
                bfs(a, b, i, places);

                for(int x = 0; x < 5; x++){
                    for(int y = 0; y < 5; y++){
                        if(dist[x][y] > 0 && dist[x][y] <= 2 && places[i][x][y] == 'P') 
                        flag = false;
                    }
                }
            }
        }

        if(flag) answer.push_back(1);
        else answer.push_back(0);
    }

    return answer;
}