[BOJ/백준][Gold5] 18428 : 감시 피하기 (C++)

https://www.acmicpc.net/problem/18428

18428번: 감시 피하기

 

 

 

[난이도] Gold5
[유형] 브루트포스

[풀이]
N이 6이므로 최대 칸의 수는 36개입니다.
장애물을 놓을 수 있는 경우의 수는 X인 칸을 vector에 저장해놓고 3중 for문을 이용해
구할 수 있습니다.

세개의 위치의 X를 O로 바꾼 뒤 학생들이 검사를 피할 수 있는지 확인해보면 됩니다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
char board[6][6];
vector<pair<int,int>> p,s;
bool check(){
    for(auto [y,x] : s){
        for(int i=0;i<4;i++){
            int cy=y,cx=x;
            while(cy>=0&&cx>=0&&cy<N&&cx<N&&board[cy][cx]!='O'){
                if(board[cy][cx]=='T') return false;
                cy+=dy[i],cx+=dx[i];
            }
        }   
    }
    return true;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf(" %c",&board[i][j]);
            if(board[i][j]=='X') p.push_back({i,j});
            if(board[i][j]=='S') s.push_back({i,j});
        }
    }
    int M = p.size();
    for(int i=0;i<M-2;i++){
        for(int j=i+1;j<M-1;j++){
            for(int k=j+1;k<M;k++){
                auto [y1,x1] = p[i];
                auto [y2,x2] = p[j];
                auto [y3,x3] = p[k];
                board[y1][x1] = board[y2][x2] = board[y3][x3] = 'O';
                if(check()) {
                    puts("YES");
                    return 0;
                }
                board[y1][x1] = board[y2][x2] = board[y3][x3] = 'X';
            }
        }
    }
    puts("NO");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/18428.cpp