[C++] Programmers 거리두기 확인하기

문제 설명

 

 

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

프로그래머스

---

내 풀이 과정

해당 문제는 한 응시자를 기준으로 맨허튼 거리가 2 내에 다른 응시자가 있는 지 검사하는 문제이다.

파티션이 없다면 단순 brute force로 풀 수 있는 문제이지만, 파티션을 만듦으로써 어떻게 좀 더 효율적인 brute force로 풀 수 있을 지에 대한 사고를 요하는 문제이다.

나같은 경우, 어디로 갈 지 결정하는 dis1(맨허튼 거리가 1인 배열), dis2(맨허튼 거리가 2인 배열) 배열을 생성하였으며 dis1을 토대로 dis2를 탐색할 지 말 지를 결정하는 알고리즘을 설계하였다.

 

1. 한 대기실 상황에서 (0, 0)부터 (5, 5)까지 전부 순회한다.

2. 그러다 P가 잡혔을 때, 검사를 실시한다.

3. 우선 맨허튼 거리가 1인 경우를 전부 검토한다.

3-1. P : 만약 다른 응시자가 있다면 바로 false를 반환

3-2. O : 만약 빈 테이블이라면 continue

3-3. X : 만약 파티션이라면 해당 위치를 경유하여 갈 수 있는 경로의 탐색 여부를 체크한다. 탐색 여부는 "notCheck" 배열에 저장하며, default는 0점이고, 2점은 탐색하지 않는다.

4. 맨허튼 거리가 2인 경우를 검토한다.

4-1. 다른 응시자가 있다면 false를 반환

4-2. notCheck가 2라면 continue

 

내 코드

#include <string>
#include <vector>

using namespace std;

const int PLACESIZE = 5;
const int dis1[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
const int dis2[8][2] = {{-2, 0}, {0, -2}, {0, 2}, {2, 0},
                  {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

bool is_good(vector<string> place, int x, int y) {
    if(place.at(x).at(y) != 'P') return true;
    int notCheck[8] = {0};
    
    // 맨허튼 거리 = 1
    for(int i = 0; i < 4; ++i) {
        int dx = x + dis1[i][0];
        int dy = y + dis1[i][1];
        if(dx < 0 || dy < 0 || dx >= PLACESIZE || dy >= PLACESIZE) continue;
        
        char element = place.at(dx).at(dy);
        if(element == 'P') return false;
        
        if(element == 'X') {
            notCheck[i] = 2;
            notCheck[4 + i - (i != 0)]++;
            notCheck[4 + i + (i != 3)]++;
        }
    }
    
    // 맨허튼 거리 = 2
    for(int i = 0; i < 8; ++i) {
        if(notCheck[i] == 2) continue; 
        int dx = x + dis2[i][0];
        int dy = y + dis2[i][1];
        if(dx < 0 || dy < 0 || dx >= PLACESIZE || dy >= PLACESIZE) continue;
        
        char element = place.at(dx).at(dy);
        if(element == 'P') return false;
    }
    
    return true;
}

int is_all_good(vector<string> place) {
    for(int i = 0; i < PLACESIZE; ++i) 
        for(int j = 0; j < PLACESIZE; ++j)
            if(!is_good(place, i, j)) return 0;
    
    return 1;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    int placeSize = places.size();
    for(int i = 0; i < placeSize; ++i)
        answer.push_back(is_all_good(places.at(i)));
    
    return answer;
}

 

핵심 코드 설명

const int dis1[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
const int dis2[8][2] = {{-2, 0}, {0, -2}, {0, 2}, {2, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};


notCheck[i] = 2;
notCheck[4 + i - (i != 0)]++;
notCheck[4 + i + (i != 3)]++;

(맨허튼 거리가 1인 위치를 탐색)

위 그림은 맨허튼 거리가 1인 위치를 탐색할 때 쓰이는 index이다.

 

 

 

(맨허튼 거리가 2인 위치를 탐색)

위 그림은 맨허튼 거리가 2인 위치를 탐색할 때 쓰이는 index이다.

• 일직선으로 된 맨허튼 거리가 2인 위치는 notCheck[i] = 2를 이용하여 탐색할 필요가 없도록 하였다.
• 대각선으로 된 맨허튼 거리가 2인 위치는 notCheck[4 + i - (i != 0)]++;와 notCheck[4 + i + (i != 3)]++;를 이용하여 값이 2가 될 때 탐색할 필요가 없도록 하였다.

---

느낀 점

확실히 예전보다는 코드를 우아하게 짜려는 욕심이 생겨서 문제를 푸는데 시간이 1.5배는 더 걸리는 것 같다.

나쁘지는 않은 습관이지만 실제 코테처럼 시간 제한을 두고 푸는 방법도 섞어서 해야겠다는 생각이 들었다.

 

그리고 다른 사람들 코드도 제각각 자신만의 알고리즘으로 풀었다.

하지만 내 방법도 나쁘지 않은 것 같다.

다만 자바를 공부하다가 c++을 다시 파다보니, 카멜 표기법과 스네이크 표기법을 자꾸 섞어쓰게 된다.

항상 맞는 말은 아니지만 자바는 카멜, c++ 스네이크로 쓰는 습관을 들이자.