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

문제 설명

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

※ 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. 

제한 사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력 예

places	result
[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]	[1, 0, 1, 1, 1]

풀이

2중 for문으로 풀면 될 것 같지만 vector<vector<string>> 의 string도 문자 하나하나 검사해야하기 때문에

결국 이 문제는 삼중 for문으로 접근하는 문제이다.

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

using namespace std;

struct point{
  int x = 0, y = 0, cnt = 0;
  
  point(int a, int b, int c){
      x = a, y = b, cnt = c;
  }
};

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

bool BFS(int a, int b, vector<string> vec){
    
    vector<vector<bool>> visit(5, vector<bool>(5, false));
  
    queue<point> Q;
    Q.push(point(a, b, 0));
    visit[a][b] = true;
    
    while(!Q.empty()){
       
        int x = Q.front().x;
        int y = Q.front().y;
        int Cnt = Q.front().cnt;
        
        Q.pop();
        
        if(Cnt == 2)
            continue;
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5){
                if(visit[nx][ny] == false){
                    if(vec[nx][ny] == 'O'){
                        visit[nx][ny] = true;
                        Q.push(point(nx, ny, Cnt + 1));
                    }
                    else if(vec[nx][ny] == 'P'){
                        return false;
                    }
                }
            }
        }
        
        
    }
    return true;
}

int CheckValue(vector<string> vec){
    for(int i = 0; i < vec.size(); i++){
        for(int j = 0; j < vec[i].size(); j++){
            if(vec[i][j] == 'P'){
                if(BFS(i, j, vec) == false){
                    return 0;
                }
            }
        }
    }
    return 1;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(int i = 0; i < places.size(); i++){
        answer.push_back(CheckValue(places[i]));
    }
    
    return answer;
}

 

다른 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool is_valid_place(const vector<string>& place)
{
    constexpr size_t N = 5;

    vector<vector<int>> is_in_use(N, vector<int>(N, false));

    int di[] = {1,-1,0,0};
    int dj[] = {0,0,1,-1};

    for(size_t i=0; i!=N; ++i)
        for(size_t j=0; j!=N; ++j)
            if(place[i][j] == 'P'){
                for(size_t k=0; k!=4; ++k){
                    size_t moved_i = i + di[k];
                    size_t moved_j = j + dj[k];

                    if(moved_i >= N || moved_j >= N)
                        continue;

                    switch(place[moved_i][moved_j]){
                        case 'P':
                            return false;
                        case 'O':
                            if(is_in_use[moved_i][moved_j])
                                return false;

                            is_in_use[moved_i][moved_j] = true;
                            break;
                        case 'X':
                            break;
                    }
                }
            }

    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer(5);
    for(size_t i=0; i!=5; ++i)
        answer[i] = is_valid_place(places[i]);
    return answer;
}