[백준/C++] 18428번: 감시 피하기

문제

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

18428번: 감시 피하기

---

문제 요약

N × N 크기의 칸으로 이루어진 복도에는 선생님, 학생, 장애물이 위치할 수 있다.

 

몇 명의 학생들이 수업시간에 몰래 복도로 빠져나왔는데, 선생님들의 감시에 들키지 않는 것이 목표이다.

 

각 선생님들은 자신의 위치에서 상,하,좌,우 4가지 방향으로 감시한다.

+ 단, 장애물 뒷 편에 숨은 학생들은 볼 수 없다.

 

복도 정보가 주어졌을 때, 정확히 3개의 장애물을 설치하여 모든 학생들이 감시를 피할 수 있는지 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <tuple>

#define MAX 6

using namespace std;

int n;
char board[MAX + 1][MAX + 1];
vector<tuple<int, int>> empties, teachers;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

// (x, y)에 선생님이 있을 때, 학생이 관측되면 true, 그렇지 않으면 false 반환 
bool check(int x, int y) {
	for (int d = 0; d < 4; d++) {
		int nx = x;
		int ny = y;

		// 범위를 벗어나면 탐색 종료
		while (nx >= 0 && ny >= 0 && nx < n && ny < n) {
			// 장애물이 있다면 그 뒤쪽은 관측 불가
			if (board[nx][ny] == 'O') break;
			
			// 학생 관측
			if (board[nx][ny] == 'S') return true;

			// 그 다음 칸 탐색
			nx += dx[d];
			ny += dy[d];
		}
	}

	// 사방을 모두 탐색했으나 학생을 발견하지 못했다면, false
	return false;
}

void dfs(int cnt) {
	// 장애물을 3개 모두 설치했을 경우, 선생님들의 좌표에서 학생 탐색
	if (cnt == 3) {
		for (int i = 0; i < teachers.size(); i++) {
			int x, y;
			tie(x, y) = teachers[i];
			// 학생 관측되었으면 계속 탐색
			if (check(x, y)) return;
		}

		// 모두 탐색했으나 학생이 관측되지 않았다면, 가능한 경우의 수가 존재하므로 탐색 종료
		cout << "YES" << "\n";
		exit(0);
	}

	for (int i = 0; i < empties.size(); i++) {
		int x, y;
		tie(x, y) = empties[i];
		
		// 장애물로 대체된 좌표는 건너뛰기
		if (board[x][y] != 'X') continue; 

		board[x][y] = 'O'; // (x, y)에 장애물 생성한다고 가정
		dfs(cnt + 1); // 탐색
		board[x][y] = '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') {
				empties.push_back({ i, j });
			}
		}
	}
	
	dfs(0);
	cout << "NO" << "\n";
	return 0;
}

---

코드 설명

복도 정보를 2차원 배열 board에 입력 받고, 선생님들의 좌표와 빈 칸의 좌표는 벡터에 따로 저장한다.

 

모든 빈 칸에 장애물을 하나씩 놓아보며 장애물 3개를 설치했을 때, 모든 학생들이 선생님들의 감시를 피할 수 있는지를 체크한다. (깊이 우선 탐색)

 

하나라도 가능한 경우의 수가 발견되면 "YES"를 출력하고 종료한다.