[프로그래머스] level2 거리두기 확인하기

단순 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;
}