거리두기 확인하기[프로그래머스]

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

int manhattan(const pair<int, int>& a, const pair<int, int>& b)
{
    return abs(a.first - b.first) + abs(a.second - b.second);
}

bool check(int startIndex, int targetIndex, const vector<string>& room, const vector<pair<int, int>>& positions)
{
    int distance = manhattan(positions[startIndex], positions[targetIndex]);    
    if(distance <= 1) return false;
    if(distance == 2)
    {
        pair<int, int> a = positions[startIndex];
        pair<int, int> b = positions[targetIndex];
        
        if(a.first == b.first)
        {
            if(room[a.first][(a.second + b.second) / 2] != 'X') return false;
        }
        else if(a.second == b.second)
        {
            if(room[(a.first + b.first) / 2][a.second] != 'X') return false;
        }
        else if(room[a.first][b.second] != 'X' || room[b.first][a.second] != 'X') return false;
    }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    vector<pair<int, int>> positions;
    for(auto& room : places)
    {
        positions.clear();
        for(int i = 0; i < room.size(); ++i)
        {
            for(int j = 0; j < room[i].size(); ++j)
            {
                if(room[i][j] == 'P')
                    positions.push_back({i, j});
            }
        }
         
        bool distanced = true;
        if(positions.size() >= 2)
        {
            for(int i = 0; i < positions.size() - 1; ++i)
            {
                for(int j = i + 1; j < positions.size(); ++j)
                {
                    distanced &= check(i, j, room, positions);
                }
            }    
        }    
        
        if(distanced) answer.push_back(1);
        else answer.push_back(0);
    }
    

    return answer;
}

#include <string>
#include <vector>

using namespace std;

// 상하좌우 탐색을 위한 방향 배열
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool dfs(int x, int y, int dist, vector<vector<bool>>& visited, const vector<string>& room) 
{
    // 1. 탐색 거리가 0보다 큰데 'P'를 만났다면 거리두기 위반!
    if(dist > 0 && room[x][y] == 'P') return false;
    
    // 2. 맨해튼 거리가 2에 도달했다면 무사히 통과한 것이므로 종료
    if(dist == 2) return true;

    // 현재 위치 방문 처리
    visited[x][y] = true;

    // 상하좌우 4방향 탐색
    for(int i = 0; i < 4; ++i) 
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 맵의 범위(5x5)를 벗어나지 않고, 아직 방문하지 않은 칸이라면
        if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !visited[nx][ny]) 
        {
            // 파티션('X')이 아닌 곳으로만 이동 가능
            if(room[nx][ny] != 'X') 
            {
                // 재귀적으로 다음 칸 탐색 (거리 1 증가)
                // 만약 위반 사례가 하나라도 발견되면 즉시 연쇄적으로 false 반환
                if(!dfs(nx, ny, dist + 1, visited, room)) return false;
            }
        }
    }
    
    return true; // 사방을 다 뒤져도 문제없으면 true
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(const auto& room : places) 
    {
        bool distanced = true;
        
        // 5x5 대기실 전체를 순회하며 'P'를 찾습니다.
        for(int i = 0; i < 5; ++i) 
        {
            for(int j = 0; j < 5; ++j) 
            {
                if(room[i][j] == 'P') 
                {
                    // 각 'P'마다 독립적인 방문 배열 생성
                    vector<vector<bool>> visited(5, vector<bool>(5, false));
                    
                    // DFS 탐색 결과 거리두기 위반이면 distanced를 false로 변경
                    if(!dfs(i, j, 0, visited, room)) 
                    {
                        distanced = false;
                        break; // 더 이상 검사할 필요 없음
                    }
                }
            }
            if(!distanced) break; // 바깥 for문도 조기 종료
        }
        
        if(distanced) answer.push_back(1);
        else answer.push_back(0);
    }

    return answer;
}