문제 링크 : 거리두기 확인하기
주어진 범위자체가 작아서 풀 수 있는 방법은 많을 것 같다.
나는 bfs를 이용해서 접근했다.
#include <string>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int check(int index, vector<vector<string>> places) {
for(int i=0 ; i<5 ; i++) {
for(int j=0 ; j<5 ; j++) {
if(places[index][i][j] == 'P') {
queue<pair<int, int>> q;
q.push({i,j});
int dist[5][5];
memset(dist, -1, sizeof(dist));
dist[i][j] = 0;
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if(dist[x][y]>=2) continue;
for(int k=0 ; k<4 ; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if(nx<0||ny<0||nx>=5||ny>=5||places[index][nx][ny]=='X'||dist[nx][ny]!=-1) continue;
if(places[index][nx][ny] == 'P') return 0;
else {
dist[nx][ny] = dist[x][y]+1;
q.push({nx, ny});
}
}
}
}
}
}
return 1;
}
vector<int> solution(vector<vector<string>> places) {
vector<int> answer;
for(int k=0 ; k<5 ; k++) {
answer.push_back(check(k, places));
}
return answer;
}