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

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

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

 

 

 

[난이도] level2
[유형] 브루트포스

[풀이]
방 한개의 칸이 5x5이기 때문에 (0,0)~(4,4) 부터 모든 점을 확인해도 시간내에 충분히 해결이 가능합니다.
만약 현재 점 (y,x)가 사람이고 아래의 P점이라면

K
K K K
K K P M M
M M M
M

M으로된 표시된 곳에 사람이 있으면서 파티션으로 막혀있지 않은지만 확인해주면 됩니다.
K로 된 곳은 이미 이전에 점을 확인하면서 체크가 되었기 때문에 확인할 필요가 없습니다.

 

#include <string>
#include <vector>
#include <cstdio>
using namespace std;


bool inRange(int y,int x){
    return (y<5 && x<5 && y>=0 && x>=0);
}

bool check(int y,int x,vector<string>& map){

    if(map[y][x]!='P') return true;

    if(inRange(y+1,x) && map[y+1][x]=='P') return false;

    if(inRange(y,x+1) && map[y][x+1]=='P') return false;

    if(inRange(y+2,x) && map[y+2][x]=='P' && map[y+1][x]!='X') return false;

    if(inRange(y,x+2) && map[y][x+2]=='P' && map[y][x+1]!='X') return false;


    if(inRange(y+1,x+1) && map[y+1][x+1]=='P'){
        if(map[y+1][x]!='X') return false;
        if(map[y][x+1]!='X') return false;
    }
    if(inRange(y+1,x-1) && map[y+1][x-1]=='P'){
        if(map[y][x-1]!='X') return false;
        if(map[y+1][x]!='X') return false;        
    }
    return true;
}

bool checkMap(vector<string>& map){
    for(int y=0;y<5;y++){
        for(int x=0;x<5;x++){
                if(!check(y,x,map)) {
                    return false;
                }
        }
    }
    return true;
}


vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int i=0;i<5;i++){
        bool ret = checkMap(places[i]);
        if(!ret) answer.push_back(0);
        else answer.push_back(1);
    }


    return answer;
}

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/거리두기 확인하기.cpp