문제
https://www.acmicpc.net/problem/18428
풀이 방법
최대 판의 개수는 n이므로 장애물 3개를 n^2개의 빈칸(최대 빈칸의 개수, 실제로는 이것보다 적음)에서 3군데를 뽑아 지정하는 경우의 수는 n^2 C 3 이고 학생의 안전(선생님의 시야에서 벗어나 있음)을 확인하는데 필요한 횟수는 2n, 최대 학생수는 n^2 이므로 시간복잡도는 O(n^9)이다. (모두 최대값으로 가정했을 경우이다. 실제로는 이보다 훨씬 적다)
이때 n은 최대 6이므로 6^9는 약 천만이므로 이 문제는 완전탐색으로 풀이가 가능하다.
실수
- 학생 모두의 안전을 확인하고 안전한 경우에는 safety를 출력했어야하는데 한명의 학생의 안전만 (맨처음) 확인하고 safety를 출력함. 수정하기 전의 코드는 아래와 같음 (기저 케이스 부분)
if (num_obstacle == 0) { // 기저 케이스
for (int i = 0; i < student_num; i++) {
if (check_safety(student_location[i][0], student_location[i][1])) {
printf("YES");
exit(0);
}
}
}
코드
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
using namespace std;
char arr[7][7];
int student_location[40][2] = { 0, };
int student_num = 0;
int n; // 판의 크기
int check_safety(int student_x, int student_y) {
// check vertical
for (int i = 1; i <= n; i++) {
if (student_x - i <= 0) {
break;
}
else if (arr[student_x - i][student_y] == 'O') {
break;
}
else if (arr[student_x - i][student_y] == 'T') {
return 0;
}
}
for (int i = 1; i <= n; i++) {
if (student_x + i > n) {
break;
}
else if (arr[student_x + i][student_y] == 'O') {
break;
}
else if (arr[student_x + i][student_y] == 'T') {
return 0;
}
}
// check horizontal
for (int i = 1; i <= n; i++) {
if (student_y - i <= 0) {
break;
}
else if (arr[student_x][student_y - i] == 'O') {
break;
}
else if (arr[student_x][student_y - i] == 'T') {
return 0;
}
}
for (int i = 1; i <= n; i++) {
if (student_y + i > n) {
break;
}
else if (arr[student_x][student_y + i] == 'O') {
break;
}
else if (arr[student_x][student_y + i] == 'T') {
return 0;
}
}
// success
return 1;
}
void dfs(int num_obstacle, int x, int y) {
if (num_obstacle == 0) { // 기저 케이스
for (int i = 0; i < student_num; i++) {
if (!check_safety(student_location[i][0], student_location[i][1])) {
return;
}
}
printf("YES");
exit(0);
}
int i = y;
int j = x + 1;
for (; i <= n; i++) { // 재귀
if (j > n) {
j = 0;
}
for (; j <= n; j++) {
if (arr[j][i] == 'X') {
arr[j][i] = 'O';
dfs(num_obstacle - 1, j, i);
arr[j][i] = 'X';
}
}
}
}
int main() {
char temp;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf(" %c", &temp);
arr[i][j] = temp;
if (temp == 'S') {
student_location[student_num][0] = i;
student_location[student_num][1] = j;
student_num++;
}
}
}
dfs(3, 1, 1);
printf("NO");
return 0;
}
기록용 블로그