프로그래머스 거리두기 확인하기 (C++)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

문제 요약

 

1. places에 5개의 대기실이 순서대로 저장되어있으며, 각 대기실은 5*5 크기의 String 배열입니다.

2. P는 사람이 앉아있음을, X는 파티션이 있음을, O는 빈자리를 뜻합니다.

3. '맨해튼 거리'를 유지하며 모든 응시자들은 사회적 거리를 유지해아합니다.

    * 맨해튼 거리 : 응시자끼리의 거리가 2이하임을 뜻함

4. 단, 응시자가 앉아있는 자리 사이가 파티션으로 막혀있으면 맨해튼 거리를 유지하지 않아도 허용됩니다.

5. 각 대기실이 거리두기를 잘 지키고 있다면 1을, 지키지 않고 있다면 0을 정답 배열에 담아 return 합니다.

 

핵심 포인트

 

맨해튼 거리를 지키지 않았을 때, 거리두기를 잘 지키고 있는지를 확인하는 것이 관건입니다.

아래 두 그림의 케이스를 유심히 잘 봐둬야합니다. 

두 칸을 띄고 앉은 경우

대각선으로 앉은 경우

 

문제 풀이

 

1. places에 저장된 원소별로 거리두기 여부를 판단합니다. 그리고 그 결과를 answer 벡터에 저장합니다.

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(auto place : places){
        answer.push_back(distance(place));
    }
    return answer;
}

 

2. 아래는 distance 코드의 전문입니다. 먼저 크게 전체를 훑어봅니다.

int my[] ={-2,-1,0,1,2}, mx[]={-2,-1,0,1,2},y=0,x=0,ny=0,nx=0,temp=0;

bool distance(vector<string> place){
    queue<pair<int,int>> q;
    for(int i=0; i<place.size(); i++){
        for(int j=0; j<place[i].size(); j++){
            if(place[i][j]=='P') q.push({i,j});
        }
    }
    while(!q.empty()){
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                ny = y+my[i];
                nx = x+mx[j];
                if(ny==y&&nx==x) continue;
                if(ny<0||ny>=5||nx<0||nx>=5) continue;
                if(abs(my[i])+abs(mx[j])>2)continue;
                if(place[ny][nx]=='P'){
                    if(ny==y){
                        temp = (nx+x)/2;
                        if(place[y][temp]!='X') return false;
                    }
                    else if(nx==x){
                        temp = (ny+y)/2;
                        if(place[temp][x]!='X') return false;
                    }
                    else{
                        if(place[ny][x]!='X'||place[y][nx]!='X') return false;
                    }
                }
            }
        }
    }
    return true;
}

 

3. distance의 첫 단락입니다.

    queue<pair<int,int>> q;
    for(int i=0; i<place.size(); i++){
        for(int j=0; j<place[i].size(); j++){
            if(place[i][j]=='P') q.push({i,j});
        }
    }

배열을 모두 돌아 'P'의 값이 저장된 위치를 큐에 담습니다. 

 

4. 다음은 while문입니다.

    while(!q.empty()){
        y = q.front().first; // 1
        x = q.front().second;
        q.pop();
        for(int i=0; i<5; i++){ // 2
            for(int j=0; j<5; j++){
                ny = y+my[i]; // 3
                nx = x+mx[j];
                if(ny==y&&nx==x) continue; // 4
                if(ny<0||ny>=5||nx<0||nx>=5) continue; // 5
                if(abs(my[i])+abs(mx[j])>2)continue; // 6
                if(place[ny][nx]=='P'){ // 7
                    if(ny==y){ // 8
                        temp = (nx+x)/2;
                        if(place[y][temp]!='X') return false;
                    }
                    else if(nx==x){ // 9
                        temp = (ny+y)/2;
                        if(place[temp][x]!='X') return false;
                    }
                    else{ // 10
                        if(place[ny][x]!='X'||place[y][nx]!='X') return false;
                    }
                }
            }
        }
    }
    return true; // 11

(1) 큐의 맨 앞에 저장된 원소를 저장하고 pop합니다.

(2) 맨해튼 거리 이하의 위치에서 'P'가 있는지 판단하기 위해, my[]와 mx[] 배열의 사이즈만큼 2중 for문을 돌립니다. 

(3) 새로운 위치 값을 ny, nx에 저장합니다.

(4) 만약 이동한 값의 변화가 없다면 continue를 합니다. (움직임의 값이 모두 0일 경우)

(5) 만약 이동한 값이 배열의 범위를 초과한다면 continue를 합니다.

(6) 만약 이동한 값이 맨해튼 거리를 초과했다면, 판단할 이유가 없으므로 continue를 합니다.

(7) 만약 이동한 값이 'P'라면...

->(8) 만약 y의 값이 같다면, place[y][(nx+x)/2]위치값이 'X'인지 판단합니다. 'X'가 아닐 경우 거리두기를 지키지 않았음을 뜻하므로, return false를 합니다. 이 과정을 통해 한 칸 간격을 띄고 앉아있는 경우도, 두 칸 간격을 띄고 앉아있는 경우도 판단이 가능합니다.

->(9) 만약 x의 값이 같다면, place[x][(ny+y)/2]의 위치값이 'X'인지 판단합니다. 나머지 설명은 8번과 동일합니다.

-> (10) 이 경우는 대각선에 사람이 있는 경우를 뜻합니다. 해당 if문에 걸리게 될 경우 return false를 합니다.

(11) while문을 빠져나왔을 경우 return true를 합니다.

 

#include <bits/stdc++.h>

using namespace std;

int my[] ={-2,-1,0,1,2}, mx[]={-2,-1,0,1,2},y=0,x=0,ny=0,nx=0,temp=0,temp2=0;

bool distance(vector<string> place){
    queue<pair<int,int>> q;
    for(int i=0; i<place.size(); i++){
        for(int j=0; j<place[i].size(); j++){
            if(place[i][j]=='P') q.push({i,j});
        }
    }
    while(!q.empty()){
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                ny = y+my[i];
                nx = x+mx[j];
                if(ny==y&&nx==x) continue;
                if(ny<0||ny>=5||nx<0||nx>=5) continue;
                if(abs(my[i])+abs(mx[j])>2)continue;
                if(place[ny][nx]=='P'){
                    if(ny==y){
                        temp = (nx+x)/2;
                        if(place[y][temp]!='X') return false;
                    }
                    else if(nx==x){
                        temp = (ny+y)/2;
                        if(place[temp][x]!='X') return false;
                    }
                    else{
                        if(place[ny][x]!='X'||place[y][nx]!='X') return false;
                    }
                }
            }
        }
    }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(auto place : places){
        answer.push_back(distance(place));
    }
    return answer;
}