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

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

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

#include <string>
#include <vector>
#define N 5
using namespace std;

int dy[8]={-1,1,0,0,-1,-1,1,1};
int dx[8]={0,0,-1,1,1,-1,1,-1};

bool isDist(vector<string> &v){
    int ny,nx;
    for (int y=0; y<N; y++){
        for (int x=0; x<N; x++){
            if (v[y][x]=='P'){
                for (int i=0; i<4; i++){
                    ny=y+dy[i]; nx=x+dx[i];
                    if (ny>=0 && ny<N && nx>=0 && nx<N){
                        if (v[ny][nx]=='P')
                            return false;
                    }
                }
                //4방향 P 인지 체크
                for (int i=4; i<8; i++){
                    ny=y+dy[i]; nx=x+dx[i];
                    if (ny>=0 && ny<N && nx>=0 && nx<N){
                        if (v[ny][nx]=='P' && (v[y][nx]=='O' || v[ny][x]=='O'))
                            return false;
                    }
                }
                //대각선 4방향 P인지 체크->P이면 주변방향 체크
                for (int i=0; i<4; i++){
                    ny=y+(2*dy[i]); nx=x+(2*dx[i]);
                    if (ny>=0 && ny<N && nx>=0 && nx<N){
                        if (v[ny][nx]=='P' && v[y+dy[i]][x+dx[i]]=='O')
                            return false;
                    }
                }
                //+2 P인지 체크, 주변 방향 체크
            }
        }
    }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for (vector<string> p: places){
        if (isDist(p))
            answer.push_back(1);
        else
            answer.push_back(0);
    }
    return answer;
}

 

구현 문제.

 

case를 3가지로 나누어서 (P 인접 동서남북 탐색, P 대각선 방향 탐색, P에서 2칸 인접 동서남북 탐색) 진행했다.

인접에 P가 있는 경우는 false, 그 외에 P가 있으면 주변 방향을 추가로 더 탐색해서 사이에 O 가 있는지 체크하는 식이다.

 

근데 이렇게 나눌 필요 없이, isvisited 배열을 만들어줘서 인접 4방향에 O 가 있을 경우 일단 배열에 방문표시를 해준다.

이후 다른 위치에서 그 위치를 탐색하게 될 때, 방문했던 O가 있으면 거리두기X 이므로 false를 리턴하는 식으로 간단히 구현 가능하다.  그러면 맨해튼 거리가 2 이하이며 사이에 테이블을 두고 있는 경우를 걸러낼 수 있다.