프로그래머스] C++ 2021 카카오 인턴십 - 거리두기 확인(Level 2)

 

 

 

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

 

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

 

 

 

1. 조건

1. String이 담긴 배열이 주어진다. 해당 String은 5X5로 무조건 고정이다.

2. P, O, X가 있으며, P는 사람의 위치, O는 빈공간, X는 칸막이 이다.

3. P1 와 P2 사이의 거리는 멘허튼 거리 2이상을 유지해야 한다.

(여기서 멘허튼 거리는 다음 공식으로 계삲할 수 있다.)

※ 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다

4. 멘허튼 거리에 P1와 P2가 포함이 될 때, 칸막이로 막혀있으면 거리를 유지한걸로 한다.

5. 거리를 유지하지 않는 곳은 0으로 유지하는 곳을 1로 배열에 담아 리턴하면 된다.

 

2. 풀이

문제를 읽고 보통 단순하게 생각하면 생각할 것이 많아져 되게 복잡해 질 수 있습니다.

해당 문제에서의 String배열은 5X5를 고정으로 주기 때문에 쉽게 풀 수 있습니다.

 

우선 멘허튼거리에 포함된 곳들을 (2, 2) 위치에서 확인해보면 다음 그림과 같이 나오게 됩니다.

P의 위치를 찿으면, 해당 위치에서 위 사진의 범위를 탐색해야 하며, 탐색과정 중 X가 만나면 더이상 탐색을 진행하지 말아야 합니다.

 

해당 범위만큼 탐색하는 알고리즘을 만들기에는 쉽지 않아보이지만 한가지 규칙이 있습니다.

(2, 2)위치에서 위, 아래, 왼쪽, 오른쪽을 탐색하면 다음과 같은 그림이 나옵니다.

그럼 위쪽으로 갔을 때 위아래 왼쪽 오른쪽을 탐색하면 다음과 같은 그림이 나옵니다.

왼쪽으로 갔을 때 위, 아래, 왼쪽, 오른쪽을 탐색하면 아래와 같은 그림이 나옵니다.

 

즉, DFS탐색을 진행하되, 깊이를 2이상 안넘기면서 탐색을 하면 되고, 해당 탐색 도중 X를 만나면 return하고,

P를 만나면 조건에 충족하지 못한다는 코드를 넣어주면 간단하게 풀리는 문제입니다.

 

 

3. 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
bool isVisit[5][5];
bool flag = false;

void checkMHL(vector<string>& place, int x, int y, int deep){
    
    for(int i = 0; i < 4; i++){
        if(deep == 2 || flag) return;
        
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        
        if(next_x >= 0 && next_x < 5 && next_y >= 0 && next_y < 5 &&
          !isVisit[next_x][next_y] && place[next_x][next_y] != 'X'){
            if(place[next_x][next_y] == 'P'){
                flag = true;
                return;
            } else {
                isVisit[next_x][next_y] = true;
                checkMHL(place, next_x, next_y, deep + 1); 
            }
        }
    }
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(auto& e : places){
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                isVisit[i][j] = false;
            }
        }
        flag = false;
        
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                if(e[i][j] == 'P' && !isVisit[i][j]){
                    isVisit[i][j] = true;
                    checkMHL(e, i, j, 0);
                }
                if(flag){
                    answer.emplace_back(0);
                    break;
                }
            }
            if(flag) break;
        }
        
        if(!flag) answer.emplace_back(1);
    }
    return answer;
}

 

문제에서 지도를 뭉탱이로 줘버려서 코드가 깔끔하게 끝나지 못한 것 같다...