[프로그래머스] 거리두기 확인하기 2021 카카오 인턴십 DFS

문제 :

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

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

 

분석 :

크기는 5X5 배열

예를 들어 입력이 2차원 배열로 주어질 때 P는 사람이고 O는 빈 테이블, X는 파티션(벽)을 의미한다.

P끼리 맨해튼 거리가 2이하가 되지 않도록 P가 거리두기를 잘 지켰는지 지켰으면 1, 그렇지 않으면 0 값을 가져

int형 배열을 리턴하는 문제였다.

 

실제 시험을 칠때에는 bfs, dfs로 보이지 않았다 ㅠ P의 위치값들을 따로 저장해 둔 뒤 P간의 거리 구하는 식으로 접근하려 했는데 대각선 이동이 어떻게 이루어져야 할지 모르겠더라 하하

 

그래서 다시 문제를 푸려고 보니까 bfs인지 보였다 그래서 다른 블로그의 코드를 참고해 풀었다.

 

우선 queue에 매번 인덱스만을 저장했었는데

queue<pair<pair<int, int>,int>> q 로 인덱스 i, j, depth까지 같이 저장한다. depth가 2 이상인 경우 아래의 for문을 돌아 탐색을 더 진행하지 않는다. 

그래서 만약 for문으로 들어가 P(사람)을 만나게 될시 무조건 거리가 2인게 위에서 보장이 되므로 거리두기를 지키지 않은 사람으로 판별을 쉽게 할 수 있다.

 

생각보다 간단하고 전형적인 bfs문제였다. 

 

c++ 코드 : 

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

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


bool bfs(int i, int j, vector<string> places){
    int visit[5][5] = { false, };
    queue<pair<pair<int, int>, int>> q; // i, j, depth
    q.push({{i, j}, 0});
    visit[i][j] = true;
    
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int depth = q.front().second;
        q.pop();
        
        if(depth == 2){ continue; }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 5 || ny >= 5|| nx < 0 || ny < 0){ continue; }
            if(visit[nx][ny] == false && places[nx][ny] == 'O'){
                visit[nx][ny] = true;
                q.push({{nx, ny}, depth + 1});
            }else if(visit[nx][ny] == false && places[nx][ny] == 'P'){
                return false;
            }
        }
    }
    return true;
}

int find_answer(vector<string> places){
    for(int i =0; i < places.size(); i++){
        for(int j = 0; j < places[i].size(); j++){
            if(places[i][j] == 'P'){
                if(bfs(i, j, places) == false){
                    return 0;
                }
            }
        }
    }
    return 1;
}

vector<int> find(vector<vector<string>> places){
    vector<int> result;
    for(int i =0; i < places.size(); i++){
        result.push_back(find_answer(places[i]));
    }
    return result;
       
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    answer = find(places);

    return answer;
}