코딩스토리

백준 17135번 - 캐슬 디펜스 본문

알고리즘/BOJ 문제 풀이

백준 17135번 - 캐슬 디펜스

kimtaehyun98 2021. 2. 21. 17:13

www.acmicpc.net/problem/17135

 

17135번: 캐슬 디펜스

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

www.acmicpc.net

다음 주 알고리즘 학회의 주제가 그래프여서 한번 풀어보았다.

 

솔직한 마음으로는 가볍게 풀어보고 괜찮은 문제다 싶으면 미팅 때 내야겠다고 생각했는데.. 

 

푸는데 2시간 걸렸다... 

 

삼성 A형 문제라는데 아직 A형 따긴 멀었네..

 

문제 자체가 어렵다기 보단 어떻게 구현해야 할지 생각하다 더 좋은 구현 방법이 자꾸 떠올라 계속해서 바꾸다 보니 오래 걸렸다.

 

문제의 퀄리티는 굉장히 좋은 것 같다. (다양한 알고리즘들이 사용됨!)

 

 

풀이

 

먼저 궁수가 무조건 3명이 있어야 하므로 조합을 통해서 궁수의 위치를 지정해줘야겠다고 생각했다.

 

이제 궁수의 위치를 지정했다면 해당 궁수들이 게임이 끝날 때까지 몇 명의 적을 죽일 수 있는지 계산해야 한다.

 

이 과정에서 가장 최단 거리인 적들을 구하기 위해 BFS를 사용했다.

 

중요한 점은 최단 거리인 적들이 중복이 가능하다는 것이다.

(계속 틀리시는 분들은 이 부분 확인해보시면 좋을듯!)

 

이 과정을 모든 적들이 사라질 때까지 반복하고, 반드시 정답은 궁수가 죽인 적들의 개수만 파악해야 한다.

 

코드

 

일단 짜고 보느라 많이 더럽지만.. 그래도 주석 달긴 했음.. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
 
struct kill {
    int dis;
    int x; 
    int y;
};
 
int n, m, d, enemy_cnt = 0, stop, temp_ans = 0, ans = 0;
int arr[17][17];
bool enemy[17][17]; // 적들이 살았는지 죽었는지를 저장하고 있는 배열
bool rem_enemy[17][17];
vector<kill>ee; // 우선순위의 적들을 가지고 있는 배열(중복 가능)
bool check[17][17];
bool all_stop = false;
vector<int>temp;
int dis[17][17];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
// 각각의 궁수들과 적들간의 최단 거리 
void bfs(int x, int y) { // 여기서 x, y는 현재 궁수의 위치
    vector<kill>v;
    queue<pii>q;
    q.push(pii(x, y));
    dis[x][y] = 0;
    check[x][y] = true;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (check[nx][ny] == false) { 
                    dis[nx][ny] = dis[x][y] + 1;
                    check[nx][ny] = true;
                    if (enemy[nx][ny] == true && dis[nx][ny] <= d) {
                        kill now = { dis[nx][ny], nx, ny };
                        if (v.empty()) v.push_back(now);
                        else { // 가장 가까운, 가장 왼쪽의 말을 가지고 있기
                            if (v[0].dis > now.dis) v[0] = now;
                            else if (v[0].dis == now.dis) {
                                if (v[0].y > now.y) v[0] = now;
                            }
                        }
                    }
                    q.push(pii(nx, ny));
                }
            }
        }
    }
    if (!v.empty()) { // 해당 궁수가 죽일 수 있는 적이 있다면
        ee.push_back(v[0]);
    }
    return;
}
 
void copy_vector() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            enemy[i][j] = rem_enemy[i][j];
        }
    }
}
 
// 궁수의 위치를 선정하는 조합 함수
void comb(int cnt, int k) {
    if (all_stop == true) return; // 컷팅 -> 모든 적을 이미 다 죽였다면 바로 종료
    if (cnt == 3) {
        stop = enemy_cnt;
        temp_ans = 0;
        copy_vector();
        while (1) {
            if (stop == 0) break; // 모든 적이 죽었다면 중지
            // bfs를 통해 해당 궁수들의 위치에서 몇 명의 적을 죽일 수 있는지 판단
            for (int i = 0; i < 3; i++) {
                memset(check, false, sizeof(check));
                memset(dis, 0, sizeof(dis));
                bfs(n, temp[i]);
            }
            // 가장 우선순위인 적들을 지움
            for (int i = 0; i < ee.size(); i++) {
                int tx = ee[i].x;
                int ty = ee[i].y;
                if (enemy[tx][ty] == true) {
                    enemy[tx][ty] = false;
                    temp_ans++;
                    stop--;
                }
            }
            ee.clear();
            // 모든 적들의 위치를 한칸씩 내려줌
            for (int i = n - 1; i >= 0; i--) {
                for (int j = m - 1; j >=0; j--) {
                    if (enemy[i][j] == true) {
                        if (n > i + 1) {
                            enemy[i][j] = false; enemy[i + 1][j] = true;
                        }
                        else {
                            enemy[i][j] = false; // 적 사라짐
                            stop--;
                        }
                    }
                }
            }
        }
        // 정답 갱신
        ans = max(temp_ans, ans);
        return;
    }
// back-tracking 통해 궁수의 위치를 조합으로 구하기
    for (int i = k; i < m; i++) {
        temp.push_back(i);
        comb(cnt + 1, i + 1);
        if (ans == enemy_cnt) {
            all_stop = true;
            return;
        }
        temp.pop_back();
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                rem_enemy[i][j] = true;
                enemy_cnt++;
            }
        }
    }
    comb(0, 0);
    cout << ans << "\n";
}
 cs
 
 
  

 

 

 

'알고리즘 > BOJ 문제 풀이' 카테고리의 다른 글

백준 17140번 - 이차원 배열과 연산  (0) 2021.03.26
백준 4485번 - 녹색 옷 입은 애가 젤다지?  (0) 2021.02.22
백준 9370번 - 미확인 도착지  (0) 2021.02.16
백준 1504번 - 특정한 최단 경로  (0) 2021.02.12
백준 5719번 - 거의 최단 경로  (0) 2021.02.11
'알고리즘/BOJ 문제 풀이' Related Articles more
Comments