단순 bfs, dfs 문제이다.
최대 2칸까지 이동할 수 있다.
다음 칸이 'X'인 경우 이동하지 않는다.
다음 칸이 'P'인 경우 거리두기가 지켜지지 않은 것이므로 false를 반환한다.
bfs로 풀면 queue의 각 원소가 현재 몇 칸 움직인 상태인지 저장해두는 작업이 필요해서 queue를 구성하는 struct를 새로 구현하게 되었다.
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#define pii pair<int, int>
using namespace std;
struct Info{
pii now;
int cnt;
};
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
int Map[6][6];
bool check(int r, int c){
queue<Info> que;
que.push({{r,c}, 0});
bool visited[6][6];
memset(visited, 0, sizeof(visited));
visited[r][c] = 1;
while(!que.empty()){
pii now = que.front().now;
int ncnt = que.front().cnt;
que.pop();
if(ncnt == 2) continue;
for(int i = 0; i< 4; i++){
int nr = now.first + dr[i];
int nc = now.second + dc[i];
// 방문했거나 막혀있으면 못감
if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
if(visited[nr][nc] || Map[nr][nc] == 'X') continue;
if(Map[nr][nc] == 'P') return false;
que.push({{nr, nc}, ncnt+1});
visited[nr][nc] = true;
}
}
return true;
}
int solve(vector<string> &place){
vector<pii > start;
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
Map[i][j] = place[i][j];
if(place[i][j] == 'P'){
start.push_back({i, j});
}
}
}
for(auto w: start){
if(!check(w.first, w.second)){
return 0;
}
}
return 1;
}
vector<int> solution(vector<vector<string>> places) {
vector<int> answer;
for(auto w: places){
answer.push_back(solve(w));
}
return answer;
}
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] level2 튜플 (C++) (0) | 2022.01.18 |
---|---|
[프로그래머스] level2 행렬 테두리 회전하기 (C++) (0) | 2022.01.16 |
[프로그래머스] level2 메뉴 리뉴얼 (C++) (0) | 2022.01.16 |
[프로그래머스] level2 수식 최대화 (C++) (0) | 2022.01.14 |
[프로그래머스] level2 뉴스 클러스터링 (0) | 2022.01.14 |