[프로그래머스][Level2] 거리두기 확인하기 c++

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

프로그래머스

 

풀이 과정

이 문제는 구현만 잘하면 간단한 문제이다.  
일단 주어진 벡터가 string형으로 되어있으므로, char 이중배열에 반복문을 돌려 넣어준다.  
그리고 사람(P)의 수를 세고, bfs문을 돌려 true 횟수가 사람의 횟수와 같으면  
다 거리두기를 잘 지키고 있다는 뜻이다.

bfs 함수에서 문제에선 거리가 2이하인데, 3이하로 설정한 이유는  
처음에 움직이지 않았는데 dist를 1로 설정해주었기 때문이다.  
0으로 설정하면 다시 되돌아가기 때문에 dist를 1로 설정해야만 방문한 곳이 된다.  
이곳에서 실수하지 않도록 조심해야된다..!

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
char arr[5][5];
int dist[5][5];

bool bfs(int x, int y){
    // dist 매번 초기화
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            dist[i][j] = 0;
        }
    }
    queue<pair<int, int>> q;
    q.push({x, y});
    dist[x][y] = 1;

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

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

            if(nx < 0 || nx > 4 || ny < 0 || ny > 4)
                continue;
            if(arr[nx][ny] != 'X' && !dist[nx][ny]){
                dist[nx][ny] = dist[x][y] + 1;
                if(arr[nx][ny] == 'P' && dist[nx][ny] <= 3) return false;
                if(dist[nx][ny] <= 3){
                    q.push({nx, ny});
                }
            }
        }
    }
    return true;
}

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

    for(int i = 0; i < 5; i++){
        int Pcnt = 0;
        for(int j = 0; j < 5; j++){
            for(int k = 0; k < 5; k++){
                arr[j][k] = places[i][j][k];
                if(arr[j][k] == 'P') Pcnt++;
            }
        }
        int res = 0;
        for(int j = 0; j < 5; j++){
            for(int k = 0; k < 5; k++){
                if(arr[j][k] == 'P'){
                    if(bfs(j, k)) res++;
                }
            }
        }
        if(Pcnt == res) answer.push_back(1);
        else answer.push_back(0);
    }

    return answer;
}