백준 18428: 감시 피하기

문제 요약

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다.

정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력한다.

문제 분류

• 브루트포스 알고리즘
• 백트래킹

문제 풀이

단순히 왼쪽 위에서부터 탐색하며 X인 곳 3곳을 적당히 찾고, 그 곳이 되는지 안되는지 다 구하면 된다.

탐색 방법이 백트래킹이지만, 그럼에도 모든 경우의 수를 따지는 브루트포스 알고리즘이 되겠다.

탐색에는 pos변수를 사용하여 pos에 1을 더해주면서 탐색했다. 결국 해당 y좌표는 pos / n, x좌표는 pos % n이 되므로 금방 구한다.

그렇게 X인 곳만 3곳을 탐색하는데, 그렇게 3곳을 찾으면 그 3곳으로 모두 막을 수 있는지 확인한다.

가로도 봐야하지만, 세로도 봐야하므로 총 두 개의 구조가 필요하다. i와 j로 이중 for문을 돌린다고 하면, ary[i][j]의 가로부분, ary[j][i]의 세로부분이 되어 동시에 O(n^2)의 복잡도로 확인 가능하다.

이전의 ary[i][j]에 따라서 가로는 r1, 세로는 r2의 변수에 매핑해주었다. S는 1, T는 2, O는 0이다. 가령 r1이 1이면서 이번에 탐색한 ary[i][j]가 T라면, S이후에 O없이 T가 나온 것이 되므로 false가 된다. 이런식으로 가능 여부를 판별한다.

for문을 돌때 처음에 r1과 r2를 0으로 초기화해주어야한다. 또한 dfs함수 호출시마다 해당 인덱스를 'O'로 만들고, 리턴 전에는 반드시 'X'로 되돌려준다(백트래킹).

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

char ary[6][6];
int n;

bool valid() {
	int r1, r2;
	for (int i = 0; i < n; i++) {
		r1 = r2 = 0;
		for (int j = 0; j < n; j++) {
			if (ary[i][j] == 'S') {
				if (r1 == 0) r1 = 1;
				else if (r1 == 2) return false;
			}
			else if (ary[i][j] == 'T') {
				if (r1 == 0) r1 = 2;
				else if (r1 == 1) return false;
			}
			else if (ary[i][j] == 'O') r1 = 0;

			if (ary[j][i] == 'S') {
				if (r2 == 0) r2 = 1;
				else if (r2 == 2) return false;
			}
			else if (ary[j][i] == 'T') {
				if (r2 == 0) r2 = 2;
				else if (r2 == 1) return false;
			}
			else if (ary[j][i] == 'O') r2 = 0;
		}
	}
	return true;
}

bool dfs(int pos, int cnt) {
	int x = pos % n;
	int y = pos / n;
	if (pos == n * n) return false;
	ary[y][x] = 'O';
	if (cnt >= 2) {
		if (valid()) return true;
		ary[y][x] = 'X';
		return false;
	}
	for (int i = 1; i + pos < n * n; i++) {
		if (ary[(pos + i) / n][(pos + i) % n] == 'X')
			if (dfs(pos + i, cnt + 1)) return true;
	}
	ary[y][x] = 'X';
	return false;
}

int main() {
	bool res = false;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			scanf(" %c", &ary[i][j]);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (ary[i][j] == 'X') {
                res = dfs(i * n + j, 0);
				if (res) break;
			}
		}
		if (res) break;
	}
	if (res) printf("YES");
	else printf("NO");
	
}