알고리즘 :: 백준 :: BFS :: 18428 :: 감시 피하기

문제

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다.
각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행한다. 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다. 또한 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정하자.
정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력한다.

문제접근

• 복도의 크기 N이 최대 6 x 6으로 굉장히 작다. 따라서 이 문제는 모든 O에 대해 3곳을 정해서 장애물을 놓고, 선생님께 들키지 않는지 여부를 확인하면 된다. (Bruteforce, BFS로 풀겠다는 이야기)
• 장애물을 두기 위해서는 해당 칸에는
  1. 선생님이 계시는 칸은 안된다.
  2. 학생이 있는 칸은 안된다.
• 둘 수 있는 모든 조합에 대해서 선생님의 위치를 queue에 넣고, pop()하면서 선생님의 위치로부터 상, 하, 좌, 우를 모두 비교해서 학생을 발견할 수 있는지 검사한다.

코드

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

static int N;
static char aisle[6][6];
static vector<pair<int, int>> teacher;

bool check() {
    for (int i = 0; i < teacher.size(); ++i) {
        int curY = teacher[i].first, curX = teacher[i].second;
        for (int y = curY - 1; y >= 0; --y) {   // 위쪽 검사
            if (aisle[y][curX] == 'O') break;
            if (aisle[y][curX] == 'S') return false;
        }
        for (int y = curY + 1; y < N; ++y) {    // 아래쪽 검사
            if (aisle[y][curX] == 'O') break;
            if (aisle[y][curX] == 'S') return false;
        }
        for (int x = curX - 1; x >= 0; --x) {   // 왼쪽 검사
            if (aisle[curY][x] == 'O') break;
            if (aisle[curY][x] == 'S') return false;
        }
        for (int x = curX + 1; x < N; ++x) {    // 오른쪽 검사
            if (aisle[curY][x] == 'O') break;
            if (aisle[curY][x] == 'S') return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    for (int y = 0; y < N; ++y) 
        for (int x = 0; x < N; ++x) {
            cin >> aisle[y][x];
            if (aisle[y][x] == 'T') teacher.push_back({y, x}); 
        }
    for (int i = 0; i < N * N; ++i)
        for (int j = i + 1; j < N * N; ++j)
            for (int k = j + 1; k < N * N; ++k) {
                int y1 = i / N, y2 = j / N, y3 = k / N;
                int x1 = i % N, x2 = j % N, x3 = k % N;
                if (aisle[y1][x1] != 'X' || aisle[y2][x2] != 'X' || aisle[y3][x3] != 'X') continue;
                aisle[y1][x1] = aisle[y2][x2] = aisle[y3][x3] = 'O';    // 고정
                if (check()) { cout << "YES\n"; return 0; }
                aisle[y1][x1] = aisle[y2][x2] = aisle[y3][x3] = 'X';    // 복원 (Bruteforce 3 원소)
            }
    cout << "NO\n";
}

결과