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

#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

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

bool bfs(int y, int x, vector<string>v)
{
    vector<vector<bool>> visited(5, vector<bool>(5, false));
    queue<tuple<int, int, int>> q;
    q.push({y, x, 0});
    visited[y][x] = 1;
    
    while(!q.empty())
    {
        auto [yy, xx, dist] = q.front();
        q.pop();
        
        if(dist == 2) continue; //맨해튼 거리 2이내만 탐색
        
        for(int i=0; i<4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if(ny < 0 || nx < 0 || ny >=5 || nx >=5 || visited[ny][nx]) continue;
            if(v[ny][nx] == 'O')
            {
                visited[ny][nx] = 1;
                q.push({ny, nx, dist+1}); //다음 좌표 및 거리 증가
            }
            else if(v[ny][nx] == 'P') return false; //범위 내 P 추가 존재
        }
    }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    bool check;
    for(auto place : places)
    {
        check = 1;
        for(int i=0; i<5; i++)
        {
            for(int j=0; j<5; j++)
            {
                if(place[i][j] == 'P')
                {
                    if(bfs(i, j, place)) continue;
                    check = 0;
                }
            }
        }
        if(check) answer.push_back(1);
        else answer.push_back(0);
    }
    return answer;
}

 

그래프 탐색으로 풀 수 있는 문제이다. (해당 코드 bfs 풀이)

현재 위치를 기준으로 P(앉아 있는 자리)를 기준으로 탐색을 시작한다.

다음 좌표 값이외에도 거리 값을 추가로 체크해야하기 때문에, tuple을 이용하여 3 값을 넘겨주었다.

 

만약 다음 좌표의 값이 빈 테이블인 'O'라면 거리를 증가시키고 추가 탐색을 이어나간다.

만약 다음 좌표의 값이 'P'라면 이미 'P'를 기준으로 탐색했기에 거리내 2명이 존재한다는 뜻이므로 false를 반환한다.

거리 2이내만 탐색하면 되므로, dist 값이 2가 되면 다음 값 탐색은 스킵한다. (기본 시작 거리 0)

이를 주어진 places 배열 내에 모든 값들에 대해 거리두기 여부를 체크해주며 해당 값 여부에 따라 answer 값을 채워준다.