📌 2021 카카오 채용연계형 인턴십
각 5*5
강의실에서 P 인 자리의 맨해튼 지수가 2 이하인 자리에 다른 P가 있는지 확인
1) 같은 행이나 열에서 맨해튼 지수가 2 이하인 경우에 거리두기가 되지 않으려면 현재 위치의 상하좌우에 X 가 없으면서 상하좌우로 한 칸씩 더 갔을 때 P가 있어야 함
2) 상하좌우 대각선 위치도 맨해튼 지수가 2 이하인데 이때 거리두기가 되지 않으려면 현재 대각선 위치가 P 이면서 그 사이가 X로 가로막혀야 함
시간복잡도로 인한 시간초과
⭐️ P로 인한 영향력을 수치화하여 표시하기 위해 별도의 5*5
int 배열 사용
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 가 가까워도 의미가 없기 때문에 영향력을 없애는 것
이 방법을 도출해낼 수 없어서 힌트 참고함..이 방법으로 풀이하지 않으면 조건문 덕지덕지의 풀이를 할 수 밖에 없다..
#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;
}