[Programmers] 거리두기 확인하기

2021 카카오 채용연계형 인턴쉽에 출제된 문제이다.

한 교실 안의 사람들이 거리두기를 잘 지키면서 앉아 있는지 확인하는 문제이다.

문제풀이 전략
거리두기가 잘 지켜졌는지 조건은 다음과 같다.

P X
X P

또는

P X P

이렇게 앉아 있어야 한다.

즉 두 사람의 거리가 2여야 하는 것이다.

또한 두 사람 사이에 X라는 칸막이가 존재해야 한다.

만약

P O
X P

로 앉았을 경우 칸막이로 완전히 분리된 것이 아니므로 거리두기를 지키지 않은 것이다.

주어지는 교실의 크기가 5X5짜리 5개로 작은 편이므로 적당히 모든 경우를 판단하면 된다.

교실 하나 기준으로 반복문을 순회하며 만약 현재 선택된 좌석이 P라면(사람이 존재한다면) 그 사람 기준으로 상하좌우를 살핀다.

만약 모두 X라면 거리두기가 잘 지켜진 것이다.

만약 네 구간 중 하나라도 P라면 거리두기가 지켜지지 않은 것이다.

만약 네 구간 중 O인 부분에 대하여 그 좌석으로부터 상하좌우를 비교해 P가 없다면 거리두기가 잘 지켜진 것이다.

위의 조건들을 코드로 풀어내면 정답이다.

코드

#include <string>
#include <vector>

using namespace std;

int xp[4] = {0,1,0,-1};
int yp[4] = {1,0,-1,0};
int zp[4] = {2,3,0,1};

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int i=0;i<places.size();i++){
        int arr[5][5];
        int flag = 1;
        for(int j=0;j<5;j++){
            for(int k=0;k<5;k++){
                arr[j][k] = 0;
            }
        }

        for(int j=0;j<places[i].size();j++){
            if(flag == 0)
                break;
            for(int k=0;k<places[i][j].size();k++){
                if(flag == 0)
                    break;
                if(places[i][j][k] == 'P'){
                    for(int t=0;t<4;t++){
                        if(flag == 0)
                            break;
                        if(j+xp[t]<0||j+xp[t]>=5||k+yp[t]<0||k+yp[t]>=5)
                            continue;
                        if(places[i][j+xp[t]][k+yp[t]] == 'P'){
                            flag = 0;
                            break;
                        }
                        if(places[i][j+xp[t]][k+yp[t]] == 'X')
                            continue;
                        if(arr[j+xp[t]][k+yp[t]] == 1)
                            continue;
                        for(int r=0;r<4;r++){
                            if(r == zp[t])
                                continue;
                            if(j+xp[t]+xp[r]<0||j+xp[t]+xp[r]>=5||k+yp[t]+yp[r]<0||k+yp[t]+yp[r]>=5)
                                continue;
                            if(places[i][j+xp[t]+xp[r]][k+yp[t]+yp[r]] == 'P'){
                                flag = 0;
                                break;
                            }
                            arr[j+xp[t]+xp[r]][k+yp[t]+yp[r]] = 1;
                        }
                    }
                }else
                    continue;
            }
        }
        answer.push_back(flag);
    }
    return answer;
}

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