[백준 17135] 캐슬 디펜스

[백준 17135] 캐슬 디펜스

문제 링크

using namespace std;
int N, M, D, answer;
int board[20][20];
int new_board[20][20];
int dx[] = { -1,0,0 };
int dy[] = { 0,-1,1 };
vector<pair<int, int>> able;
vector<pair<int, int>> candidates;
int visit[20][20];
void input() {
    cin >> N >> M >> D;  // 세로, 가로
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < M; i++) {
        able.push_back({N, i});
    }
}
int check() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (new_board[i][j]) return false;
        }
    }
    return true;
}
void copy_board() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            new_board[i][j] = board[i][j];
        }
    }
}
void play() {

  int score = 0;
  copy_board();            // map 초기화

  while (1) {              // 게임이 끝날 때 까지
    if (check()) break;  // 모든 적을 죽이면 끝
    int will_killed[20][20];
    int chk[20][20];
    memset(will_killed, 0, sizeof(will_killed));

    for (int archer = 0; archer < 3; archer++) {
      // kill enemies -> 거리, 제일 왼쪽
      // bfs
      queue<vector<int>> q;
      pair<int, int> kill = {99, 99};
      memset(chk, 0, sizeof(chk));
      q.push({candidates[archer].first, candidates[archer].second});
      chk[candidates[archer].first][candidates[archer].second] = 1;
      int dist = 0;

      while (!q.empty()) {
        dist++;
        if (dist > D) break;
        int qsize = q.size();

        while (qsize--){
            int top_x = q.front()[0];
            int top_y = q.front()[1];
            q.pop();

            for (int k = 0; k < 3; k++) {
                int nx = top_x + dx[k];
                int ny = top_y + dy[k];
                if (nx < 0 || ny < 0 || ny >= M || nx >= N || chk[nx][ny]) continue;
                q.push({nx, ny});
                chk[nx][ny] = 1;

                if (new_board[nx][ny] && kill.second > ny) {
                    kill = {nx, ny};
                }
            }
        }

        if(kill.first != 99) {
          will_killed[kill.first][kill.second] = 1;
          break;
        }
        
      }
    }
    // 제일 왼쪽의, 거리가 제일 적은 애 찾았음.
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (will_killed[i][j]) {
                new_board[i][j] = 0;
                score++;
            }
        }
    }

    // 한 칸 씩 내리기
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < M; j++) {
            new_board[i][j] = new_board[i - 1][j];
        }
    }

    for (int i = 0; i < M; i++) {
        new_board[0][i] = 0;
    }
  }

  answer = max(answer, score);
}
void dfs(int idx) {
    // 궁수 세 명 배치 완료
    if (candidates.size() == 3) {

        play();
        return;
    }

    for (int i = idx; i < able.size(); i++) {
        int x = able[i].first;
        int y = able[i].second;
        if (!visit[x][y]) {
            candidates.push_back({x, y});
            visit[x][y] = 1;
            dfs(i + 1);
            candidates.pop_back();
            visit[x][y] = 0;
        }
    }
}
void solve() {
    dfs(0);
    cout << answer << endl;
}

int main() {
    input();
    solve();
    return 0;
}

• dfs + bfs, 시뮬레이션 문제
• 하루종일 했다,,,, 이ㅓㅏㅁㄹㄴ;만ㅇ 너무.. 스트레스받앗던문제 ㅜ 못하겠어서 걍 답보고ㅅ함
• 처음에는 우선순위 큐로 제일 가까운 적들을 업데이트 하면서 진행하려고 했는데 정렬이 좀 복잡해서 그냥 dfs + bfs로 풀었다
• 조합으로 M중 3가지의 경우의 수를 모두 구하고,
• 궁수의 위치가 결정이 됐으면 가장 가까운 적들을 해치우고, 한 줄씩 내려주면 된다.
• 이 때, 바로 없애면 안된다. 중복된 적을 허용 해 주어야 한다.
• qsize만큼 돌아야지만 답이 통과가 되는데, dist를 bfs돌릴 때 하나씩 업데이트 해 주고, pop할때 dist가 D를 넘는지 확인하는 방식으로 하니까 통과가 안된다. 웨죠