Logo냥냠감자기술 블로그
Skip to Content
AlgorithmBruteforce (11)감시 피하기
작성일: 2024-01-12

문제

백준 18428 - 감시 피하기 

  • 난이도: 골드5
  • 알고리즘: 브루트포스

코드

#include <iostream> #include <vector> using namespace std; const int dx[4]={1, 0, -1, 0}; const int dy[4]={0, -1, 0, 1}; int boardSize; bool dfs(vector<vector<char>>& board, int y, int x, int direction) { if(x<0 || x>boardSize-1 || y<0 || y>boardSize-1) { return true; } if(board[y][x]=='S') { return false; } else if(board[y][x]=='O') { return true; } else { return dfs(board, y+dy[direction], x+dx[direction], direction); } } bool checkAvail(vector<vector<char>>& board) { for(int i=0; i<boardSize; i++) { for(int j=0; j<boardSize; j++) { for(int direction=0; direction<4; direction++) { if(board[i][j]!='T') { continue; } if(!dfs(board, i, j, direction)) { return false; } } } } return true; } bool putBlocks(vector<vector<char>>& board, int remainToChoose, int y, int x) { if(remainToChoose==0) { return checkAvail(board); } if(x==boardSize) { x=0; y++; } if(y==boardSize) { return false; } if(board[y][x]!='X') { return putBlocks(board, remainToChoose, y, x+1); } bool ret=false; board[y][x]='O'; ret=ret || putBlocks(board, remainToChoose-1, y, x+1); board[y][x]='X'; ret=ret || putBlocks(board, remainToChoose, y, x+1); return ret; } int main() { cin>>boardSize; vector<vector<char>> board(boardSize, vector<char>(boardSize)); for(int i=0; i<boardSize; i++) { for(int j=0; j<boardSize; j++) { cin>>board[i][j]; } } if(putBlocks(board, 3, 0, 0)) { cout<<"YES"; } else { cout<<"NO"; } }

회고

알고리즘 공부하는 내용을 웹 페이지에 정리하려 한다. 예제를 적기 위해 문제를 풀었다.

브루트포스 문제는 언제 풀든지 얻어가는 것이 있는 것 같다.