(C++) - 백준(BOJ) 18428번 : 감시피하기

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

18428번: 감시 피하기

backtracking 이용한 brute force 문제였습니다.

 

 

 

📕 풀이방법

 n과 m의 응용문제였습니다.

 

📔 입력 및 초기화

 board라는 2차원 배열 변수에 적절히 입력받습니다. 입력 도중 'T', 'X', 'S'가 나온 곳의 행,열 좌표를 각자 다른 vector 변수에 저장합니다.

 

 

📔 풀이과정

 1. dfs를 수행합니다. 3개의 장애물을 조합의 형태로 board를 바꿔줍니다. 순서 상관있게 3개의 'O'를 'X'인 자리에 배치해봅니다. 3개의 장애물을 모두 놓았으면 선생님의 좌표를 중심으로 상,하,좌,우 4방향으로 뻗어가며 볼 수 있는 곳을 확인해줍니다.

 

 2. 선생님이 볼 수 있는 위치에 학생이 있다면 성공하지 못했으므로 바로 dfs함수를 종료합니다.

 

 3. 성공했다면 isSafe를 true로 만들어주고 종료합니다.

 

 

📔 정답출력

 isSafe가 true라면 YES를 아니라면 NO를 출력합니다.

---

 

 

📕 Code

#include <bits/stdc++.h>
using namespace std;
struct Coords {int r,c;};
char board[6][6];
int dr[] = {0,0,-1,1};
int dc[] = {1,-1,0,0};
int n, canSee[6][6] ;
bool isSafe;
vector <Coords> emptySpace, teachers, students;


void checkArea(){
    for(auto t : teachers){
        for(int dir = 0; dir < 4; dir++){
            int nr = t.r;
            int nc = t.c;
            canSee[nr][nc] = 1;
            while(1){
                nr += dr[dir];
                nc += dc[dir];
                if(0 > nr || nr >= n || 0 > nc || nc >= n) break;
                if(board[nr][nc] == 'O') break;
                canSee[nr][nc] = 1;
            }
        }
    }
}

void dfs(int depth, int idx) {
	if (depth == 3) {
        memset(canSee,0,sizeof(canSee));
        
        checkArea();

        for(auto s : students)
            if(canSee[s.r][s.c]) return;

        isSafe = true;
        return;
	}

    for(int i = idx; i < emptySpace.size(); i++){
        int r = emptySpace[i].r;
        int c = emptySpace[i].c;
        board[r][c] = 'O';
        dfs(depth+1, i + 1);
        board[r][c] = 'X';
    }
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'T') teachers.push_back({ i,j });
			if (board[i][j] == 'X') emptySpace.push_back({ i,j });
            if (board[i][j] == 'S') students.push_back({ i,j });
		}
	}

	dfs(0, 0);
    if(isSafe) cout << "YES";
    else cout << "NO";
}

 

📕 Test Case

몇 가지 예제를 직접 작성해봤습니다. 도움되었으면 좋겠습니다.

 

3
S X X
S X X
T X S
NO

3
T S X
T X S
T X S
NO

3
T X S
T X S
T X S
YES

5
T X X X S
T X X X X
X X S X X
X X X X S
X X T X S
YES