[BFS] 거리두기 확인하기 - 2021 카카오 채용연계형 인턴십

해결 방법

맨해튼 거리의 개념을 모르더라도 단순히 BFS 알고리즘으로 해결할 수 있다. 자신을 제외한 응시자들 중에서 BFS 거리가 2이하인 응시자가 있다면 거리두기를 준수하지 않은 것으로 판단하면 된다.

주의할 점이 있다면 이 문제는 테스트케이스 5개가 있기 때문에 queue와 방문 배열을 초기화하는 작업이 필요하다.

그리고 연산 횟수를 줄이기 위해 거리두기 준수 여부를 나타내는 변수를 활용하여 거리 두기를 준수하지 않다는 사실이 확정났다면 해당 케이스에 대해서는 추가적인 연산을 수행하지 않도록 했다. 또, BFS 깊이가 3을 넘어가는 경우에는 queue에 구조체를 넣지 않았다.

 

 

소스 코드

#include <string>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;

struct Point {
    int x;
    int y;
    int d; // BFS 깊이
};

int dx[4]={0, 0, -1, 1};
int dy[4]={1, -1, 0, 0};
queue<Point> q;
char map[5][5];
bool visited[5][5];

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int t=0;t<5;t++){
        int obs=1; // 준수 여부 - 기본 true(1)
        for(int x=0;x<5;x++) for(int y=0;y<5;y++) map[x][y]=places[t][x][y]; // map에 저장
        for(int x=0;x<5;x++){
            for(int y=0;y<5;y++){
                if(!obs||map[x][y]!='P') continue; // 준수 여부가 확정났거나 P자리가 아닌 경우 제외
                memset(visited, false, sizeof(visited));
                q=queue<Point>();
                q.push({x, y, 0});
                visited[x][y]=true;
                while(!q.empty()){
                    Point f = q.front();
                    q.pop();
                    if(!(f.x==x&&f.y==y)&&f.d<=2&&map[f.x][f.y]=='P'){ // 다른 응시자와의 거리가 2이하인 경우
                        obs=0; // 준수 안함 - false(0)
                        break;
                    }
                    for(int k=0;k<4;k++){
                        int nx=f.x+dx[k];
                        int ny=f.y+dy[k];
                        if(nx<0||nx>=5||ny<0||ny>=5) continue;
                        if(!visited[nx][ny]&&map[nx][ny]!='X'){
                            visited[nx][ny]=true;
                            if(f.d<2) q.push({nx, ny, f.d+1}); // BFS 깊이가 3이상인 경우 제외
                        }
                    }
                }
            }
        }
        answer.push_back(obs);
    }
    return answer;
}

 

테스트케이스 31개 모두 정답