거리두기 확인하기(20분)

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

구현 아이디어 4분 구현 16분

풀이

1. places를 돌며 응시자가 앉아있는 경우에 상, 하, 좌, 우 빈 자리를 확인하여 빈 자리라면 empty_places 배열에 true를 넣는다.
2. 다음 응시자가 앉아있는 칸에 도착했을 때, 상, 하, 좌, 우에 빈 자리가 확인된다면 거리두기를 지키지 않았다는 뜻이다.

• 빈 자리 확인과 더불어 "PP"와 같이 바로 옆에 앉아있는 경우를 고려해야 한다.

#include <string>
#include <vector>

using namespace std;

bool empty_places[5][5];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

bool check(const vector<string>& places)
{
    int N = places.size();
    int M = places[0].size();
    
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < M; ++j)
            if(places[i][j] == 'P')
            {
                // 상, 하, 좌, 우 검사하여 빈 테이블이 있다면 return false;
                for(int k = 0; k < 4; ++k)
                {
                    int check_i = i + dr[k];
                    int check_j = j + dc[k];
                    
                    if(check_i < 0 || check_j < 0 || check_i >= N || check_j >= M) continue;
                    
                    // 상, 하, 좌, 우에 빈 테이블로 표시된 부분이 있다면 false 리턴.
                    if(empty_places[check_i][check_j]) return false;
                    
                    // PP 이렇게 연속으로 앉아있는 경우도 고려해야 함.
                    if(places[check_i][check_j] == 'P') return false;
                    
                    if(places[check_i][check_j] == 'O')
                        empty_places[check_i][check_j] = true;
                }
            }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(int i = 0; i < 5; ++i)
    {
        for(int j = 0; j < 5; ++j)
            for(int k = 0; k < 5; ++k)
                empty_places[j][k] = false;
        
        if(check(places[i]))
            answer.push_back(1);
        else answer.push_back(0);
    }
    
    return answer;
}