2021 카카오 채용연계형 인턴십
거리두기가 지켜지고 있는지 확인하는 문제입니다.
P가 있는곳에서 BFS를 통해 2칸을 확인합니다.
2칸안에 P가 존재하면 거리두기가 지켜지지 않은 경우입니다.
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int result;
vector<vector<char> > v;
vector<vector<bool> > visit;
vector<vector<bool> > falseVisit(5, vector<bool>(5, false));
queue<pair<pair<int, int>, int> > q;
vector<int> solution(vector<vector<string>> places) {
int y, x, c;
vector<char> temp;
vector<int> answer;
for(int i=0; i<places.size(); ++i){
result = 1;
v.clear();
for(int j=0; j<5; ++j){
for(int k=0; k<5; ++k){
temp.push_back(places[i][j][k]);
}
v.push_back(temp);
temp.clear();
}
for(int i=0; i<5; ++i){
for(int j=0; j<5; ++j){
if(v[i][j] == 'P'){
visit = falseVisit;
q.push({{i, j}, 0});
while(!q.empty()){
y = q.front().first.first;
x = q.front().first.second;
c = q.front().second;
q.pop();
visit[y][x] =true;
if(c != 0 && c < 3 && v[y][x] == 'P'){
result = 0;
while(!q.empty()){
q.pop();
}
} else if(c == 3){
continue;
}
if(y-1 >= 0 && v[y-1][x] != 'X' && !visit[y-1][x]){
q.push({{y-1, x}, c+1});
}
if(x-1 >= 0 && v[y][x-1] != 'X' && !visit[y][x-1]){
q.push({{y, x-1}, c+1});
}
if(y+1 < 5 && v[y+1][x] != 'X' && !visit[y+1][x]){
q.push({{y+1, x}, c+1});
}
if(x+1 < 5 && v[y][x+1] != 'X' && !visit[y][x+1]){
q.push({{y, x+1}, c+1});
}
}
}
}
if(result == 0){
break;
}
cout << endl;
}
answer.push_back(result);
}
return answer;
}
'알고리즘' 카테고리의 다른 글
[C++] 프로그래머스 - 불량 사용자 (0) | 2021.09.14 |
---|---|
[C++] 프로그래머스 - 셔틀버스 (0) | 2021.09.14 |
[C++] 프로그래머스 - 추석 트래픽 (0) | 2021.09.14 |
[JavaScript] 프로그래머스 - 키패드 누르기 (0) | 2021.09.14 |
[JavaScript] 프로그래머스 - 직업군 추천하기 (0) | 2021.08.28 |