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

문제

 

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

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

 

 

 

문제풀이

 

현재 탐색하려는 대상이 'P', 'O'일 때만 따지면 된다.

탐색하는 대상 기준으로 대상, 상, 하, 좌, 우 칸에서 'P'가 오는 개수를 센다.

'P'가 2개 이상이 있다면 맨해튼 거리가 2 이하이며, 파티션으로 막히지 않은 부분이 있다는 의미이다.

 

'P' 'X'

'O' 'P'

인 경우 탐색 대상이 'O'일 때 거리두기를 지키지 않은 것을 판별할 수 있다.

 

'P' 'P'

인 경우 탐색 대상이 'P'일 때 거리두기를 지키지 않은 것을 판별할 수 있다.

 

'P' 'X'

'O' 'X'

'P' 'X'

인 경우 탐색 대상이 'O'일 때 거리두기를 지키지 않은 것을 판별할 수 있다.

코드

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

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

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer(places.size(), 1);    

    for (int idx = 0; idx < places.size(); ++idx) {
        int N = places[idx].size();
        int M = places[idx][0].size();
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < M; ++x) {
                if (places[idx][y][x] == 'X') continue;

                int cnt(0);
                if (places[idx][y][x] == 'P') ++cnt;
                for (int move = 0; move < 4; ++move) {
                    int ny = y + dy[move];
                    int nx = x + dx[move];
                    if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
                    if (places[idx][ny][nx] == 'P') ++cnt;
                }
                if (cnt > 1) {
                    answer[idx] = 0;
                    y = places[idx].size();
                    break;
                }
            }
        }
    }

    return answer;
}