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

김영한·2021년 8월 20일
0

알고리즘

목록 보기
61/74

문제 링크 : 거리두기 확인하기

[문제 접근]

주어진 범위자체가 작아서 풀 수 있는 방법은 많을 것 같다.
나는 bfs를 이용해서 접근했다.

  1. 탐색 중 응시자일 때 맨해튼 거리를 지키고 있는지 check해주었다.
  2. 맨해튼 거리를 측정하기 위해 dist라는 배열을 대기실마다 초기화하여 사용했다.
  3. 거리가 2이하까지 탐색했고 그 안에 응시자를 만나게되면 바로 0을 리턴해주었다.
  4. 파티션을 만나면 탐색을 중지하여 맨허튼 거리가 2이하 이지만 파티션으로 분리되어있을 때 가능하게끔 구현했다.

[소스 코드]

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

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

int check(int index, vector<vector<string>> places) {
    for(int i=0 ; i<5 ; i++) {
        for(int j=0 ; j<5 ; j++) {
            if(places[index][i][j] == 'P') {
                queue<pair<int, int>> q;
                q.push({i,j});
                int dist[5][5];
                memset(dist, -1, sizeof(dist));
                dist[i][j] = 0;
                while(!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    if(dist[x][y]>=2) continue;
                    for(int k=0 ; k<4 ; k++) {
                        int nx = x+dx[k];
                        int ny = y+dy[k];
                        
                        if(nx<0||ny<0||nx>=5||ny>=5||places[index][nx][ny]=='X'||dist[nx][ny]!=-1) continue;
                        if(places[index][nx][ny] == 'P') return 0;
                        else {
                            dist[nx][ny] = dist[x][y]+1;
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }
    return 1;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(int k=0 ; k<5 ; k++) {
        answer.push_back(check(k, places));
    }
    
    return answer;
}

0개의 댓글