(C++) - 프로그래머스(2021 카카오 채용연계형 인턴십) : 거리두기 확인하기

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

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

bfs로 풀었습니다.

 

풀이방법

 1. 모든 수험자에 대해 bfs를 수행합니다. bfs를 수행했을 때 확인되는 지점들이 모여생긴 한 공간이라고 생각합니다. 한 대기실에는 여러 영역이 존재할 수도 있습니다. 따라서 모든 대기실의 지점을 확인해 아직 확인 안한 수험자를 시작 노드로 하여 bfs를 수행하는 것입니다.

 

 2. 한 공간에서는 맨해튼 거리가 2이하인 수험자들이 배치되어 있어야 합니다.

 

 3. 모든 영역에서 맨해튼 거리를 모두가 지키고 있다면 해당 대기실에는 1을 아니라면 0을 answer에 push_back해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int ck[5][5];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int bfs(int i, int j, vector<string>place){
    queue <pii> q;
    q.push({i,j});
    ck[i][j] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int dir = 0; dir < 4; dir++){
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(0 > nx || nx >= 5 || 0 > ny || ny >= 5) continue;
            if(place[nx][ny] == 'X' || ck[nx][ny]) continue;
            ck[nx][ny] = ck[x][y] + 1;
            if(place[nx][ny] == 'P'){
                if(ck[nx][ny] <= 3) return 0;
            }
            q.push({nx,ny});
        }
    }
    return 1;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int i = 0; i < places.size(); i++){
        int flag = 1;
        for(int j = 0; j < places[i].size(); j++){
            for(int k = 0; k < places[i][j].size(); k++){
                memset(ck,0,sizeof(ck));
                if(places[i][j][k]=='P' && !ck[j][k] ){
                    flag = bfs(j,k,places[i]);
                    if(!flag) break;
                }
            }
            if(!flag) break;
        }
        if(!flag) answer.push_back(0);
        else answer.push_back(1);
    }
    return answer;
}