프로그래머스 - 거리두기 확인하기 (C++)

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

프로그래머스

 

접근법

- 처음 봤을 때는 bfs 한번으로 해결하기 위해 고민했으나 각 P 별로 bfs를 돌아도 N이 워낙 작아서 시간초과가 나지 않는 문제이다.

플로이드-워셜도 생각이 났는데 플로이드 워셜은 행렬에서 사용해본적이 없고 간선의 비용이 주어지면 행렬로 표현하는 것이라 결이 다르다고 생각이 된다. 

각 대기실은 5x5크기이기 때문에 bfs의 시간복잡도는 25이고, 모든 칸에 P가 존재하는 경우의 수를 생각해도 25 * 25 = 625 그리고 대기실은 총 5개 존재하므로  * 5 를 해도 3125밖에 안된다. 

O(M * N^2 * (K)) 이다. 여기서 M은 대기실 개수 N은 대기실 사이즈 K는 P의 수이다.  

아무래도 의도는 조건을 통해 푸는 것 같다. 내풀이의 경우 최악의 상황은 N^4이기 때문에 N이 커지면 사용할 수없다.

 

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

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

vector<int> answer;

bool bfs(vector<string> place, int startx, int starty){
    bool visited[26][26] = {false,};

    vector<pair<int, int>> players;
    queue<pair<pair<int, int>, int>> q;
    q.push({{startx, starty}, 0});
    visited[startx][starty] = true;

    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
        if(place[x][y] == 'P'){
            if(x != startx || y != starty)
                if(cnt < 3){
                   // cout << cnt << endl;
                    return false;  
            }
        }
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 5 && nx > -1 && ny < 5 && ny > -1 && visited[nx][ny] == false && place[nx][ny] != 'X'){
                visited[nx][ny] = true;
                q.push({{nx, ny}, cnt + 1});
            }
        }
    }
    
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            cout << visited[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
        return true;

}

vector<int> solution(vector<vector<string>> places) {
    for(int i = 0; i < places.size(); i++){
        bool flag = true;
        for(int j = 0; j < places[i].size(); j++){
            for(int k = 0; k < places[i][j].size(); k++){
                if(places[i][j][k] == 'P'){
                    cout << i + 1 << endl;
                    if(!bfs(places[i], j, k)){ // 지키지 않음 확인
                        flag = false;
                        break;
                    }
                }
            }
            if(!flag) break;
        }
        if(flag) answer.push_back(1);
        else answer.push_back(0);
    }
    
    return answer;
}