[프로그래머스/Level 2] 거리두기 확인하기 (C++)

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

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

카카오 기출

 

입력값의 크기가 최대 5로 고정 되어 있어서 BFS를 이용한 완전 탐색으로 문제를 해결했다.

문제에서 맨해튼 거리를 요구하므로, 이는 1칸씩 이동했을 때 누적한 거리와 같다.

따라서 BFS를 이용하면 현재 응시자가 다음 응시자를 만나는 최단 거리를 보장할 수 있다.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Info {
    int x, y, d; // 좌표와 현재 거리
};

vector<string> Place; // 각 대기실을 저장할 전역 벡터
vector<int> answer;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};


bool BFS(int sx, int sy) {
    // 방문 좌표 체크, 거리두기 가능 여부
    bool visit[5][5] = {false, }, flag = true;
    queue<Info> q;
    q.push({ sx, sy, 0 });
    visit[sx][sy] = true;

    while(!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int d = q.front().d;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 범위를 벗어나는 경우
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            // 이미 방문했거나, 파티션으로 막혀 있는 경우
            if(visit[nx][ny] || Place[nx][ny] == 'X') continue;
            // 응시자와 만난 경우
            if(Place[nx][ny] == 'P') {
                // 맨해튼 거리가 2 이하면 거리두기 실패
                if(d + 1 <= 2) {
                    flag = false;
                    break;
                }
            }

            q.push({ nx, ny, d + 1 });
            visit[nx][ny] = true;
        }
        
        // 한 명이라도 거리두기를 지키지 못했으므로 BFS 탐색 바로 종료
        if(!flag) break;
    }

    return flag;
}

vector<int> solution(vector<vector<string>> places) {
    for(auto p : places) {
        bool flag = true;
        Place = p; // 현재 대기실을 전역 벡터에 저장
        
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                if(p[i][j] == 'P') {
                    if(!BFS(i, j)) {
                        flag = false; // 거리두기 실패
                        break;
                    }
                }
            }
            
            // 한 명이라도 거리두기를 지키지 못했으므로 해당 대기실 거리두기 체크를 바로 종료
            if(!flag) break;
        }
        
        // 0 : 거리두기 실패, 1 : 거리두기 성공
        if(!flag) answer.push_back(0);
        else answer.push_back(1);
    }
    
    return answer;
}