백준 18428번 감시 피하기 C++ 백트래킹, BFS, 완전 탐색, 구현, 시뮬레이션

리뷰

 

벽을 정확히 3개를 세워 학생들이 선생님의 눈을 피할 수 있게 하는 완전 탐색 문제

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

 

문제 풀이

1. 전역 변수로 맵의 변의 크기 n, 정답 여부체크용 ans, 맵 lst, 방문 여부 v, 방향배열, 선생님 정보 T를 설정해 준다.
2. input 함수를 통해 n값과 맵의 정보를 받는다, 이때 T가 입력된 경우 구조체 Pos타입 벡터 T에 추가해 준다.
3. dfs 함수를 통해 완전 탐색을 돌려준다. 매개변수 level은 벽 설치 개수, row는 탐색을 재개할 행 정보다.
4. 벽의 개수가 3개가 되면 기저조건에 해당된다, bfs를 통해 시뮬레이션을 돌려준다.
5. 선생님을 순회하며 4방향으로 감시를 시작한다, 범위를 벗어나거나 벽을 만나기 전까지 해당 방향을 쭉 탐색한다.
6. 만약 S를 마주쳤다면 선생에게 포착된 것이므로 바로 return 처리 해주도록 한다.
7. 만약 모든 학생이 모든 선생님의 감시에 포착되지 않았다면 ans를 true로 변경하고 return 처리 해준다.
8. ans가 true인 경우 dfs를 진행할 필요가 없으므로 재귀에서 계속 빠져나오면 된다.
9. 모든 탐색이 종료된 후 ans가 true일 경우 YES출력, 아닐 경우 NO를 출력해 준다.

 

참고 사항

재귀 실행 전 벽을 설치한 위치는 O로 바꿔주고, 재귀가 종료된 후 다시 X로 바꿔준다.

 

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;
int n, ans = false;
char lst[6][6];
int v[6][6];
int dx[] = { 0,  0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y;
};

vector<Pos> T;

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
			if (lst[i][j] == 'T') T.push_back({ i, j });
		}
	}
}

void bfs() {
	for (Pos pos : T) {
		int cx = pos.x, cy = pos.y;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			while (0 <= nx && nx < n && 0 <= ny && ny < n && lst[nx][ny] != 'O') {
				if (lst[nx][ny] == 'S') return;
				nx += dx[i];
				ny += dy[i];
			}
		}
	}
	ans = true;
	return;
}

void dfs(int level, int row) {
	if (ans) return;
	if (level == 3) {
		bfs();
		return;
	}

	for (int i = row; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (lst[i][j] != 'X') continue;
			if (v[i][j]) continue;
			v[i][j] = 1;
			lst[i][j] = 'O';
			dfs(level + 1, i);
			lst[i][j] = 'X';
			v[i][j] = 0;
		}
	}
}

void solution() {
	dfs(0, 0);
}

int main() {
	input();
	solution();
	if (ans) cout << "YES";
	else cout << "NO";
}