2021 KAKAO INTERNSHIP [거리두기 확인하기] [C++]

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

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

---

문제 요약

5x5 책상이 존재하는 공간에 학생들은 2칸(상, 하, 좌, 우) 이내에 있을 경우 위험하기 때문에

2칸 넘게 자리를 확보하며 앉아있는지 확인하는 문제.

 

---

나의 풀이

5 x 5 지도가 주어졌기 때문에 BFS를 이용하여 한 학생 주위에 존재하는 자리를 확인하면 된다

 

나의 경우 (0,0) 부터 (4,4)까지 순회를 하며 사람이 존재할 경우 해당 사람 기준으로 2칸 이내에 다른 사람이 있는지만 살펴주었다 

불필요한 순회가 있긴 하지만 시간복잡도를 전혀 고려하지 않아도 되는 정도의 크기이기 때문에 반복수행을 하면서 

2칸 이내에 사람이 있을 경우 바로 return false를 해주고

모든 순회를 마쳣다면 모두 거리두기를 지킨 것이므로 return true를 해준식으로 구현했다

 

---

소스코드

#include<bits/stdc++.h>
using namespace std;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool isValid(int r , int c){
    return r>=0&&r<5&&c>=0&&c<5;
}
int isSafe(vector<string> room){

    vector<pair<int,int>> people;

    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(room[i][j]=='P'){
                people.push_back({i,j});
            }
        }
    }

    for(pair<int,int> person : people){
        bool chk[5][5];
        memset(chk,false,sizeof(chk));
        queue<pair<int,pair<int,int>>> q; 
        int sr = person.first;
        int sc = person.second;
        q.push({2,{sr,sc}});
        chk[sr][sc]=true;

        while(!q.empty()){
            int val = q.front().first;
            int cr = q.front().second.first;
            int cc = q.front().second.second;
            q.pop();
            for(int i=0;i<4;i++){
                int nr = cr+dx[i];
                int nc = cc+dy[i];
                if(isValid(nr,nc)&&!chk[nr][nc]&&val>0){
                    char next_seat = room[nr][nc];
                    if(next_seat!='X'){
                        if(next_seat=='P'){
                            return 0;
                        }
                        chk[nr][nc]=true;
                        q.push({val-1,{nr,nc}});
                    }
                }
            }
        }
    }
    return 1;
}
vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(auto room : places){
        answer.push_back(isSafe(room));
    }
    return answer;
}