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

 

카카오 채용연계형 인턴십 문제이다.

2021년 당시에는 풀지도 못한 문제였는데.

 

2년이 지난 지금, 20분만에 풀었다.

 

나는 BFS를 이용해 풀었는데, depth를 계산하다가 맨헤튼 거리가 2가 넘어가는 순간 실패로 책정했다.

#include <string>
#include <vector>
#include <cstring>
#include <queue>

// 20
using namespace std;

bool visit[5][5];

int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

bool bfs(vector<string>& place, int sx, int sy) {
    
    
    queue<pair<pair<int ,int>, int>> que;
    que.push({{sx, sy}, 0});
    visit[sx][sy] = true;
    
    
    while(!que.empty()) {
        
        int x = que.front().first.first;
        int y = que.front().first.second;
        int d = que.front().second;
        
        que.pop();
        
        
        for(int i = 0; i < 4; i++) {
            int tx = x + mx[i];
            int ty = y + my[i];
            
            if(tx < 0 || tx >= 5 || ty < 0 || ty >= 5)
                continue;
            
            if(!visit[tx][ty]) {
                
                if(place[tx][ty] == 'O') {
                    que.push({{tx, ty}, d + 1});
                    visit[tx][ty] = true;
                } else if(place[tx][ty] == 'P') {
                    if(d + 1 <= 2)
                        return false;
                    else {
                        que.push({{tx, ty}, d + 1});
                        visit[tx][ty] = true;
                    }
                }
            }
    
            
        }
        
    }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    
    for(auto place : places) {
                
        bool flag = true;
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                if(place[i][j] == 'P') {
                    memset(visit, 0, sizeof(visit));
                    if(!bfs(place, i, j)) {
                        flag = false;
                    }
                }
            }
        }
        
        if(flag)
            answer.push_back(1);
        else
            answer.push_back(0);
        
    }
    
    
    return answer;
}

 

 

다른 분의 풀이도 봤는데, 신기한 풀이가 있었다.

그 분은 모든 2차원 반복문을 돌며, P를 만날 때면 상하좌우를 체크해준다. (갈 수 있는 O일 경우) 이게 끝이다.

 

문제에서 주어진 맨헤튼거리가 2이상이면 거리두기에 실패한 것이고, 맨헤튼거리가 2이상이라는건

한쪽에서 한칸으로 갈 수 있다면 다른 한 쪽에서도 한칸으로 갈 수 있는 것이다.

이 원리를 이용하신 것..! 감탄했다.