[백준]캐슬디펜스

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

17135번: 캐슬 디펜스

 

틀린이유를 아직 못찾았다. --> 궁수의 조합을 구할때 for문을 열로해야되는데 행으로 했다. ㅡㅡ;;하 ***

순서는 1.조합으로 3명의 궁수 선택

2.한 궁수씩 bfs를 통해 적을 잡는다. 동시에 잡을수도있으니까 2로 표시하고 0으로 바까줌

3.잡으면 큐를 비우고 리턴을 해서 다음 궁수로 넘어간다. . .

#배울점은 많았던 문제였던것 같다. 

1.단계별로 bfs 카운트하는 것.

2.여러가지 예외사항들이 있었다. 동시에 잡을수있고, 왼쪽부터 잡으며 그래서 바로 0으로 못하고 2로 해놓는등의 시뮬

3.한 궁수가 끝나고 다음 궁수로 넘어갈때 큐를 비워줘야한다는 것 

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
/*
1.모든적이 격자에서 제외되면 게임이 끝남. 제거할수 있는 적의 최대수를 구해라.
1.N열에 궁수를 3명 배치. --> 완전 탐색.조합으로 3개의 궁수자리 선택.
2.자리에서부터 왼쪽을 우선순위로 잡을수 있는 적 탐색.
3.bfs로 좌 상 하 순으로 탐색해서 한마리 잡음. D까지만 잡을수 있음.
4.잡고나서 적군 전진.
5.반복 적군이 없어질때 까지.
**예외사항 : 할때마다 q를 비워줘야하는것
*/
 
int N, M, D; //거리제한
int map[16][16];
int back[16][16]; //배열을 바꾸면 안되기때문에 백업매열 사용
bool isV[16]; //bfs마다 초기화
int ans = -1e9;
queue<pair<int, int> > q;
int dr[] = { 0,-1,0 }, dc[] = { -1,0,1 }; //좌상우(우선순위맞춰줌)
 
void MOVE() {
    for (int i = N - 1; i >= 0; i--) {
        //성쪽에서부터 
        for (int j = 0; j < M; j++) {
            back[i + 1][j] = back[i][j];
        }
    }
    for (int j = 0; j < M; j++) {
        back[0][j] = 0;
        back[N][j] = 0;
    }
}
 
int bfs(int r,int c) {
    int isV[16][16];
    memset(isV, 0, sizeof(isV));
    q.push(make_pair(r, c));
    int cnt = 1; //단계를 체크!!!
    while (!q.empty()) {
        int qlen = q.size();
        while (qlen--) { //단계별로 bfs를 진행함 !
            int r = q.front().first, c = q.front().second;
            q.pop();
            
            if (back[r][c] == 1) { while (!q.empty()) { q.pop(); } back[r][c] = 2; return 1; } //잡음(2로표시)
            if (back[r][c] == 2) { while (!q.empty()) { q.pop(); } return 0; } //동시에 같은걸 잡은놈
 
            for (int i = 0; i < 3; i++) {
                int nr = r + dr[i], nc = c + dc[i];
                if (nr < 0 || nc < 0 || nr >= N || nc >= M || isV[nr][nc] == 1) continue;
                
                q.push(make_pair(nr, nc));
                isV[nr][nc] = 1;
            }
        }
        if (cnt == D) { while (!q.empty()) { q.pop(); } return 0; } //큐를 비워야함 남아있으면 다음에 영향을 줌
        cnt++; //단계수 check
    }
}
 
void dfs(int start,int len) {
    if (len == 3) {
        //back으로 탐색진행(초기화를 해줘야함)
        memcpy(back, map, sizeof(back));
        
        int a[3] = { 0 }, s = 0;
        for (int i = 0; i < M; i++) {
            if (isV[i] == true) { a[s] = i; s++; }
        }//출발점을 배열에 저장
 
        int cnt = 0; //잡은 적군의 수
        while (1) {
            bool END = true;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (back[i][j] == 1) { j = M; i = N; END = false; }
                }
            } // 남은 적군이 있는지를 확인
            if (END == true) break;
 
            //궁수마다 각각 탐색을 진행. 다같이 하면 return문을 적용하기가 애매함.
            cnt += bfs(N - 1, a[0]);
            cnt += bfs(N - 1, a[1]);
            cnt += bfs(N - 1, a[2]);
            MOVE();
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) { //한타임 지나고 잡았던 적군을 죽는 걸로 표시.
                    if (back[i][j] == 2) back[i][j] = 0;
                }
            }
        }
        if (cnt >= ans) ans = cnt;
        return;
    }
 
    //조합
    for (int i = start; i < M; i++) {
        if (isV[i] == false) {
            isV[i] = true;
            dfs(i, len + 1);
            isV[i] = false;
        }
    }
}
 
int main()
{    
    cin >> N >> M >> D; //N번째에 궁수 있다고 가정.
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> map[i][j];
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}