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

✅ LV.2

📌 2021 카카오 채용연계형 인턴십

✏️ 1차 솔루션

각 5*5 강의실에서 P 인 자리의 맨해튼 지수가 2 이하인 자리에 다른 P가 있는지 확인
1) 같은 행이나 열에서 맨해튼 지수가 2 이하인 경우에 거리두기가 되지 않으려면 현재 위치의 상하좌우에 X 가 없으면서 상하좌우로 한 칸씩 더 갔을 때 P가 있어야 함
2) 상하좌우 대각선 위치도 맨해튼 지수가 2 이하인데 이때 거리두기가 되지 않으려면 현재 대각선 위치가 P 이면서 그 사이가 X로 가로막혀야 함

🚨 trouble

시간복잡도로 인한 시간초과

✏️ 최종 솔루션

⭐️ P로 인한 영향력을 수치화하여 표시하기 위해 별도의 5*5 int 배열 사용

1. 강의실의 자리가 X 이면 해당 자리의 board 값을 10으로 갱신
2. 강의실의 자리가 P 이면 해당 자리와 상하좌우의 board 값에 -1
3. 한 강의실을 모두 탐색하면 board 값 중에 -2 보다 작은 값의 존재 여부로 거리두기 성공, 실패 판단

📌 self feedback

P 칸에서 맨해튼 거리가 2가 되는 칸을 모두 탐색하는 것이 아니라 문제에서 거리두기가 되는 경우와 그렇지 않은 경우를 수치화해서 풀이해야 했음

❗️ 맨해튼 거리에 있는 모든 자리의 값을 -1 해야한다고 생각할 수 있지만, 맨해튼 거리의 값을 모두 -1 한다면
P O O P 로 구성되어 있을 때 -1 -2 -2 -1 로 정작 P 끼리는 맨해튼 거리가 2보다 큼에도 불구하고 거리두기가 지켜지지 않는다고 판단하게 됨
상하좌우만 판단해도 자기 자신도 -1 해주기 때문에 만약 P O P O 처럼 맨해튼 거리 2 이하에 P가 있을 때, -1 -2 -1 -1 으로 거리두기가 지켜지지 않는 형식의 board 가 생성됨
또한, X 자리의 board 값을 10으로 갱신하는 것은 어차피 X 가 있으면 P 가 가까워도 의미가 없기 때문에 영향력을 없애는 것

이 방법을 도출해낼 수 없어서 힌트 참고함..이 방법으로 풀이하지 않으면 조건문 덕지덕지의 풀이를 할 수 밖에 없다..

✏️ 최종 code

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

using namespace std;

// 상하좌우
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int board[5][5];

void mn(int x, int y) {
    board[x][y]-=1;
    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) continue;
        
        board[nx][ny]-=1;
    }
}

bool chk(vector<string> &v) {
    memset(board,0,sizeof(board));
    
    for(int i=0;i<5;i++) {
        for(int j=0;j<5;j++) {
            if(v[i][j]=='X') board[i][j]=10;
            else if(v[i][j]=='P') {
                mn(i,j);
            }
        
        }
    }
    
    for(int i=0;i<5;i++) {
        for(int j=0;j<5;j++) {
            if(board[i][j]<=-2) return false;
        }
    }
    
    return true;
}

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