[Algorithm] Programmers :: 거리두기 확인하기

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

프로그래머스

struct Node
{
    int y;
    int x;
    int count;
};
 
int visited[6][6] = { false };
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
bool BFS(int startRoom, int startY, int startX, vector<vector<string>>& places)
{
    memset(visited, false, sizeof(visited));
 
    queue<Node> q;
    q.push({ startY,startX,0 });
    visited[startY][startX] = true;
    places[startRoom][startY][startX] = '?';
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curCount = q.front().count;
        q.pop();
 
        if (places[startRoom][curY][curX] == 'P')
        {
            places[startRoom][startY][startX] = 'P';
            return false;
        }
 
        if (curCount == 2) continue;
 
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= 5) continue;
            if (nextX < 0 || nextX >= 5) continue;
            if (visited[nextY][nextX]) continue;
            if (places[startRoom][nextY][nextX] == 'X') continue; // 파티션으로 막혀있으면
 
            visited[nextY][nextX] = true;
            q.push({ nextY,nextX,curCount + 1 });
        }
    }
 
    places[startRoom][startY][startX] = 'P';
    return true;
}
 
vector<int> solution(vector<vector<string>> places) 
{
    vector<int> answer;
 
    for (int i = 0; i < 5; ++i) // 대기실
    {
        bool isBreak = false;
 
        for (int j = 0; j < 5; ++j) // 대기실의 행
        {
            for (int k = 0; k < 5; ++k)
            {
                if (places[i][j][k] == 'P')
                {
                    if (!BFS(i, j, k, places))
                    {
                        isBreak = true;
                        break;
                    }
                }
            }
 
            if (isBreak) break;
        }
 
        if (isBreak) answer.push_back(0);
        else answer.push_back(1);
    }
 
    return answer;
}

기본적으로 값들이 작아서 탐색이 아니라 if문으로도 풀수 있긴한데, 만약 조건이 이것저것 붙는다면 탐색으로 푸는 방법을 알아야할 것이다.