[BOJ] 백준 18428 감시 피하기 c++ (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/18428

18428번: 감시 피하기

---

풀이

dfs로 장애물을 찾고 해당 경우가 조건에 맞는지 판별하는 대표적인 백트래킹 문제이다.

 

처음 입력을 받을때 teacher(T), none(X)를 vector에 저장해두고 none 자리의 경우의 수를 dfs로 찾는다.

 

이때 다른 문제와 좀 다른 점은, vector에 push와 pop을 하는대신 바로 arr에 O와 X문자열을 대입해준 점이다.

3개를 찾으면 check_avoid 함수를 통해 정답에 맞는지 판별한다.

 

DFS

void dfs(int idx, int cnt){
	if(cnt == 3) {
		for(auto elem: teacher) {
			if(!check_avoid(elem.first, elem.second)) {
				return;
			}
		}
		cout << "YES\n";
		exit(0);
	}
	for(int i = idx; i < none.size(); i++) {
		arr[none[i].first][none[i].second] = 'O';
		dfs(i+1, cnt+1);
		arr[none[i].first][none[i].second] = 'X';
	}
}

백트래킹

check_avoid역시 대표적인 4방향 탐색이다.

다만 장애물을 만나기 전까지 찾으므로 while문을 돌려 장애물(O)을 만난 경우 break해준다.

bool check_avoid(int row, int col) {
	for(int i = 0; i < 4; i++) {
		int nrow = row;
		int ncol = col;
		while(nrow >= 0 && nrow < N && ncol >= 0 && ncol < N) {
			nrow += dx[i];
			ncol += dy[i];
			if(arr[nrow][ncol] == 'O') 
				break;
			if(arr[nrow][ncol] == 'S')
				return false;
		}
	}
	return true;
}

---

코드

#include <bits/stdc++.h>

using namespace std;

int N;
char arr[6][6];
vector<pair<int, int>> teacher, none;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool check_avoid(int row, int col) {
	for(int i = 0; i < 4; i++) {
		int nrow = row;
		int ncol = col;
		while(nrow >= 0 && nrow < N && ncol >= 0 && ncol < N) {
			nrow += dx[i];
			ncol += dy[i];
			if(arr[nrow][ncol] == 'O') 
				break;
			if(arr[nrow][ncol] == 'S')
				return false;
		}
	}
	return true;
}

void dfs(int idx, int cnt){
	if(cnt == 3) {
		for(auto elem: teacher) {
			if(!check_avoid(elem.first, elem.second)) {
				return;
			}
		}
		cout << "YES\n";
		exit(0);
	}
	for(int i = idx; i < none.size(); i++) {
		arr[none[i].first][none[i].second] = 'O';
		dfs(i+1, cnt+1);
		arr[none[i].first][none[i].second] = 'X';
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> arr[i][j];
			if(arr[i][j] == 'T')
				teacher.push_back({i, j});
			else if(arr[i][j] == 'X') {
				none.push_back({i, j});
			}
		}
	}
	dfs(0, 0);
	cout << "NO\n";

	return 0;
}