https://www.acmicpc.net/problem/18428
18428번: 감시 피하기
NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복
www.acmicpc.net
[난이도] 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
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold5] 19539 : 사과나무 (C++) (0) | 2022.11.06 |
|---|---|
| [BOJ/백준][Gold5] 15661 : 링크와 스타트 (C++) (0) | 2022.11.06 |
| [BOJ/백준][Gold5] 17218 : 비밀번호 만들기 (C++) (0) | 2022.11.06 |
| [BOJ/백준][Gold4] 2253 : 점프 (C++) (0) | 2022.11.06 |
| [BOJ/백준][Silver3] 16967 : 배열 복원하기 (C++) (0) | 2022.11.06 |