프로그래머스 lv2 - 거리두기 확인하기

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

프로그래머스

 

맨해튼 거리 : x좌표 차이 + y좌표 차이

 

✏️ 문제 풀이

< 너비 우선 탐색 선정 >

탐색 대상이 된 응시자를 기준으로, 다른 응시자에게 향하는 최적의 경로를 찾는 것이 아닌!
맨해튼 거리가 2 이하일 때 도달할 수 있는지의 여부를 확인하면 되기 때문에
너비 우선 탐색을 사용하고자 하였다.

• 너비 우선 탐색 필수 요소 : 이동 방향 정의 

int dirX[4] = {1, 0, -1, 0};
int dirY[4] = {0, 1, 0, -1};

 

• 너비 우선 탐색 필수 요소 : 방문 여부 확인

int visited[5][5];
for(int i = 0; i < 5; i++){
    for(int j = 0; j < 5; j++){
        visited[i][j] = 0;
    }
}

 

< 조건 설정 >

1. 이동할 위치가 범위 내인가
2. 방문한 적이 있는가
3. 해당 위치가 탐색을 시작한 지점으로부터 맨해튼 거리 2 이하인가 
4. 해당 위치가 벽인가 아닌가

if(isBoundary(nextX, nextY)){  
	if(visited[nextX][nextY] == 0 && calcDistance(people[i], next) < 3){
		if(seats[nextX][nextY] != 'X'){
			que.push(next);
            visited[nextX][nextY] = 1;
        }
    }
}

 

< 종료 조건 >

끝까지 탐색하기 전에 내가 아닌 다른 응시자에게 도달한 경우

if(seats[nowX][nowY] == 'P' && !(nowX==sX && nowY==sY)){
    return false;
}

 

---

⏳ 학습하며 겪었던 문제점

고려해야 하는 조건이 많아서 코드가 복잡해지는 것을 느꼈다.
최대한 심플하게 짜기 위해서 시간을 많이 투자했다.

보완할 점, vector를 매개변수로 넘겨주기

코딩 테스트 역량을 기르기 위해 공부하던 교재에서는 주로 전역변수로 배열을 선언하고 이를 모든 함수에서 이용했었다.
이때의 배움이 습관적으로 코드에 적용되었다.

index 만으로 충분히 해당 위치의 값을 탐색할 수 있기 때문에 별도의 배열이 필요하지 않았으나
나는 전역변수에 seats 배열을 선언하고 사용하였다.

그러나 별도의 배열을 선언할 필요 없이 위의 코드처럼
벡터 자체를 너비 우선 탐색을 수행하는 함수에 매개변수로 넣어주면 훨씬 간단해진다.

 

보완할 점, 문제에서 주어진 조건을 어떻게 더 간단하게 풀지 고민해 보기

문제에서는 맨해튼 거리 2 이하인 경우를 고려하라고 명시되어 있기 때문에
나는 해당 조건을 충실하게 지키기 위해 몰두했다.

그런데 상하좌우만 비교한 풀이가 있었다.
이게 어떻게 정답으로 인정되는 건지 처음에는 이해가 잘 되지 않았다.

switch(place[moved_i][moved_j]){
	case 'P':
		return false;
	case 'O':
		if(is_in_use[moved_i][moved_j])
		return false;
        
		is_in_use[moved_i][moved_j] = true;
		break;
	case 'X':
		break;
}

 

정답이 되는 원리는 다음과 같다.

• 맨해튼 거리 1 (상하좌우)를 탐색한다.
• 탐색 위치가 O(빈자리)인 경우, 방문 여부를 확인한다.
• 방문한 적이 있는 경우 false를 반환한다.
• 방문한 적이 없는 경우, 방문 여부를 true로 변경한다.

나는 한 인물에 대해서 맨해튼 2의 탐색을 끝낸 후, 방문 여부를 초기화했다.
반대로, 위의 코드는 각 인물에 대해 맨해튼 1에 대해 탐색하고 이를 초기화하지 않는다.

따라서 탐색된 위치가  O일 때, 이미 방문한 적이 있다면
맨해튼 거리 1에 대한 범위가 교차하는 것을 의미하기 때문이다.

맨해튼 거리 2

격자의 중앙이 탐색 대상이라고 할 때, 맨해튼 거리 2까지의 범위를 나타낸 것이다.
다른 응시자와의 맨해튼 거리 2 내부에 존재해서는 안된다. (파티션은 일단 제외)

만약 다른 응시자가 맨해튼 거리 2 내부에 존재한다면,
아래의 초록과 노랑 응시자처럼 맨해튼 거리 1의 탐색 결과가 무조건 교차하게 되는 것이다.

맨해튼 거리 1에 대한 탐색 결과 예시

 

---

🖥️ 전체 코드

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

int seats[5][5];
vector<pair<int, int>> people;

int dirX[4] = {1, 0, -1, 0};
int dirY[4] = {0, 1, 0, -1};

bool isBoundary(int x, int y){
    return(x >= 0 && x < 5 && y >= 0 && y < 5);
}

int calcDistance(pair<int, int> p1, pair<int, int> p2){
    return abs(p1.first-p2.first) + abs(p1.second-p2.second);
}

bool checkBetween(){
    queue<pair<int, int>> que;
    int visited[5][5];

    for(int i = 0; i < people.size(); i++){
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                visited[i][j] = 0;
            }
        }

        que.push(people[i]);
        int sX = people[i].first;
        int sY = people[i].second;
        visited[sX][sY] = 1;
        while(!que.empty()){
            int nowX = que.front().first;
            int nowY = que.front().second;
            que.pop();
            if(seats[nowX][nowY] == 'P' && !(nowX==sX && nowY==sY)){
                return false;
            }
            for(int j = 0; j < 4; j++){
                int nextX = nowX+dirX[j];
                int nextY = nowY+dirY[j];
                auto next = make_pair(nextX, nextY);
                if(isBoundary(nextX, nextY)){  
                    if(visited[nextX][nextY] == 0 && calcDistance(people[i], next) < 3){
                        if(seats[nextX][nextY] != 'X'){
                            que.push(next);
                            visited[nextX][nextY] = 1;
                        }
                    }
                }                                                              
            }
        }
    }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int room = 0; room < 5; room++){
        for(int line = 0; line < 5; line++){
            for(int pos = 0; pos < 5; pos++){
                char seat = places[room][line][pos];
                seats[line][pos] = seat;
                if(seat == 'P'){
                    people.push_back(make_pair(line, pos));
                }
            }      
        }
        if(checkBetween()){
            answer.push_back(1);
        }
        else{
            answer.push_back(0);
        }
        people.clear();
    }
    return answer;
}