문제

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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net



http://boj.kr/71aa3dc2114d434298d0db61392052b3

Baekjoon Online JudgeBaekjoon Online Judgeboj.kr


nCr() :m개의 좌표 조합을 구한뒤

simul() : 각 조합마다 전염을 시뮬해볼 배열(임시공간)에 초기상태를 memmove로 가져온 후 dfs()로 전염시간시뮬을 돌려보고

find_best() : 임시공간 전수조사해서 0이 있는지 확인후 0이 있으면 전염에 실패했으니까 중간에 함수빠져나오고 0이 없으면 이 임시공간에서 최댓값을 찾은후 내가 찾은 최선의 경우와 비교해서 더 작은쪽을 최선의 경우로 업데이트함


이런 접근으로 했는데 지금 어디서 실수했는지 5%에서 틀렸습니다가 뜨는데 어디를 잘못찾고있는걸까요?




#include <stdio.h>
#include <string.h>
#define SIZE 51
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
char dy[4] = {0,1,-1,0};
char dx[4] = {1,0,0,-1};
short board[SIZE][SIZE]; int n, m;
short update[SIZE][SIZE];

void input();

static inline int isSafe(int y, int x) {
return (y>=0 && y<n && x>=0 && x<n);
}

char disease[10][2]; int rear; //바이러스의 개수 M(1 ≤ M ≤ 10)
void simul();
int arr[3];
int find_best(); int best;
void dfs(int y, int x, int step);
void nCr(int idx, int cnt);


void test();
int main() {
input();
nCr(0,0);
if(best < n*n+1) printf("%d\n", best-1);
else printf("-1\n");
return 0;
}

void input() {
scanf("%d %d", &n, &m); best = n*n+1;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
scanf(" %hd", &board[i][j]);
if(board[i][j] == 1) board[i][j] = -1;
else if(board[i][j] == 2) {
board[i][j] = 0;
disease[rear][0] = i; disease[rear++][1] = j;
}
}
}
}

void nCr(int idx, int cnt) {
if(cnt == m) {
simul();
// printf("%d\n", best);
// test();
return;
}
for(int i=idx; i<rear; i++) {
arr[cnt] = i;
nCr(i+1, cnt+1);
}
}

void simul() {
memmove(update, board, sizeof(board));
for(int i=0; i<m; i++) {
dfs(disease[arr[i]][0], disease[arr[i]][1], 1);
}
find_best();
}

int find_best() {
int tmp = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(update[i][j] == 0) return -1;
tmp = max(tmp, update[i][j]);
}
}
best = min(best, tmp);
}

void dfs(int y, int x, int step) {
if(update[y][x] > 0 && update[y][x] <= step) return;
update[y][x] = step;

for(int i=0; i<4; i++) {
int py = y+dy[i], px = x+dx[i];
if(isSafe(py, px) && update[py][px] != -1) {
dfs(py, px, step+1);
}
}
}

void test() {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
printf("%2d ",board[i][j]);
}
printf("\t");
for(int j=0; j<n; j++) {
printf("%2d ",update[i][j]);
}
printf("\n");
}
printf("\n");
}