문제 출처

1. 문제설명

  • 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
  • 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
    • 맨해튼 거리는 쉽게 말해 모눈종이의 칸 수 이다.
  • 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.


2. 입/출력

  • places의 5개 행의 각 행은 하나의 대기실 구조
  • places의 열 길이(대기실 세로 길이) = 5
    • P,O,X로 이루어진 문자열
      • P : 응시자가 앉아있는 자리
      • O : 빈 테이블
      • X : 파티션
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담아 리턴


3. 문제 분류

  • Simulation, BFS


4. 알고리즘 설계

  • 5x5크기이므로, 하나씩 탐색하면서 P라면 BFS를 수행하면 된다.
    • 만약 결과가 true이면 맨해튼 거리 2 이하에 앉아있는 다른 사람이 있다는 의미
  • BFS
    • 현재 위치 x, y와 거리 정보를 담은 구조체를 큐를 통해 관리하였다.
    • 만약 현재 큐에서 꺼낸 거리가 2라면 건너뛴다.
      • 더이상 탐색할 필요가 없다.
    • 그렇지 않다면 4방향 탐색을 진행한다.
      • 다음 이동 칸의 값이 O라면 거리를 1 증가시켜 큐에 담는다.
      • 다음 칸이 P라면 위에 2라면 건너뛴다의 전이므로 false를 리턴한다.
    • 큐가 비어있을 때까지 false를 리턴하지 않았다면 거리두기를 지키고 있는 것이다.


5. 전체 코드

#include <bits/stdc++.h>
using namespace std;

struct pos {int x, y, d;};

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

vector<string> board;

bool bfs(int x, int y) {
    bool vis[5][5] = {false,};
    queue<pos> q;
    q.push({x, y, 0});
    vis[x][y] = true;
    
    while(!q.empty()) {
        pos cur = q.front();
        q.pop();
        
        if(cur.d == 2) continue;
        
        for(int dir=0; dir<4; dir++) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            
            if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
            
            if(!vis[nx][ny]) {
                if(board[nx][ny] == 'O') {
                    q.push({nx, ny, cur.d + 1});
                    vis[nx][ny] = true;
                }
                else if(board[nx][ny] == 'P') return false;
            }
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(auto& cur : places) { 
        board.assign(cur.begin(), cur.end());
        bool flag = true;
        
        for(int i=0; i<5 && flag; i++) {
            for(int j=0; j<5; j++) {
                if(board[i][j] == 'P') {
                    if(!bfs(i, j)) {
                        flag = false;
                        break;
                    }
                }
            }
        }
        
        if(flag) answer.push_back(1);
        else answer.push_back(0);
    }
    
    return answer;
}


4. 소감

  • 약간의 조건을 추가한 BFS의 유형이었다.