그냥 1차원적인 구현 문제이다. 

감시카메라의 갯수가 8개를 넘지않으므로 

각 카메라에 대한 회전 경우의수 4가지 (0도 90도 180도 270도)

4^8 = O(65536 * n^2(사각지역을 구할때 8*8밖에 되지않아 그냥 0인곳을 매번 다 탐색했다))

본인은 구현하지 않았지만 생각해보면 다음 5번 경우는 회전을해도 그대로니 

               5번 케이스인 경우는 제외하고 탐색해준다면 더빠를것 같다. 

다른분들은 더 효율적으로 짠것같기는 한데 나는 무려 20MS나 나왔다... ㅠ

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




<code>


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
//pda_pro12
#include<iostream>
#include<vector>
#define INT 0x7fff0000
using namespace std;
 
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }, n, m;   // 0: 위 // 1: 오른 // 2: 아래 // 3: 왼 
bool Map[9][9][4]; int tmp[9][9], Orign[9][9];
vector<pair<int, int>> v;  // 감시카메라의 좌표정보 저장(1~8) 
vector<int> Rotate; // 카메라 회전정보 저장(O(4^v.size()))
int ans = INT;    // 최소값 산출을 위해 초기값 INT MAX값으로 214748347 설정
 
int Min(int a, int b) {
    return (a < b) ? a : b; 
}
 
int Recovery() {   // 감시처리 전의 상태로 복구함과 동시에 사각지역 탐색 
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tmp[i][j] == 0) cnt++;
            tmp[i][j] = Orign[i][j];
        }
    }
    return cnt;
}
 
void View_Camera(int num, int flag) {  // 몇번 카메라가 몇도 회전 했는지 Prameter로 받는다. 
    int x = v[num].first;  int y = v[num].second;
    for (int i = 0; i < 4; i++) {
        if (Map[x][y][i]) {
            int nx = x + dx[(i + flag) % 4];  int ny = y + dy[(i + flag) % 4];
            while (tmp[nx][ny] != 6 && nx >= 0 && nx < n && ny >= 0 && ny < m) { // 범위를 벗어나지 않거나 이미 감시한 지역(9)이고, 빈칸일경우 
                if (tmp[nx][ny] == 0) tmp[nx][ny] = 9;
                nx += dx[(i + flag) % 4];  ny += dy[(i + flag) % 4];
            }
        }
    }
    return;
}
 
void dfs(int cnt) {
    if (cnt == v.size()) { // 카메라에 대한 회전 정보가 카메라 갯수와 같아젔다면
        for (int i = 0; i < Rotate.size(); i++) // 회전정보만큼 카메라 돌려서 감시지역 처리해주기
            View_Camera(i, Rotate[i]);
        ans = Min(ans, Recovery());
        return;
    }
    for (int i = 0; i < 4; i++) { // 0: No rotate 1: 90  2: 180 3: 270
        Rotate.push_back(i);
        dfs(cnt + 1);
        Rotate.pop_back();
    }
    return;
}
 
int main() {
    cin >> n >> m;   // n = row  ,    m = col 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tmp[i][j];
            Orign[i][j] = tmp[i][j];
            if (!tmp[i][j] || tmp[i][j] == 6)     continue; // 0이나 벽일경우 
            v.push_back(make_pair(i, j));  // Camera Direction (row, col); 
 
            switch (tmp[i][j]) {  // No1 ~ No5 Camera Direction input
            case 1: // 1type Camera   --> 초기 방향에 대한 정보를 저장해둔다 
                Map[i][j][1] = true;
                break;
            case 2:    //2type Camera
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 3:  // 3type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                break;
            case 4:   // 4type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 5:
                for (int a = 0; a < 4; a++)
                    Map[i][j][a] = true;
                break;
            }
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}


< STL의 유혹을 떨처버린 Code >


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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
//pda_pro12
#include<iostream>
#define INT 0x7fff0000
 
using namespace std;
 
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }, n, m;   // 0: 위 // 1: 오른 // 2: 아래 // 3: 왼 
bool Map[9][9][4]; int tmp[9][9], Orign[9][9];
 
template<class T>
class _vector {
public:
    int _size; 
    int capacity; 
    T* arr; 
    _vector() {
        _size = 0; 
        capacity = 32; 
        arr = new T[capacity]; 
    }
    _vector(int k) {
        _size = k; 
        capacity = k; 
        arr = new T[k]; 
    }
    ~_vector() {
        delete[] arr; 
    }
    void clear() {
        delete[] arr; 
        _size = 0; 
        capacity = 32; 
        arr = new T[capacity]; 
    }
    
    void resize(int k) {
        T* temp; 
        temp = new T[k];
        for (int i = 0; i < _size; ++i) 
            temp[i] = arr[i]; 
        delete[] arr; 
        arr = temp; 
        _size = capacity = k; 
    }
 
    int size() const {
        return _size; 
    }
 
    T* begin() const {
        return &arr[0]; 
    }
 
    T* end() const {
        return &arr[0] + _size; 
    }
 
    void push_back(T val) {
        if (capacity == _size) {
            resize(_size * 2); 
            _size /= 2; 
        }
        arr[_size++] = val; 
    }
 
    void pop_back() {
        _size--; 
    }
 
    T& operator[](int idx) {
        return arr[idx]; 
    }
 
    T operator[](int idx) const{
        return arr[idx]; 
    }
};
 
_vector<pair<int, int>> v;  // 감시카메라의 좌표정보 저장(1~8) 
_vector<int> Rotate; // 카메라 회전정보 저장(O(4^v.size()))
 
int ans = INT;    // 최소값 산출을 위해 초기값 INT MAX값으로 214748347 설정
 
int Min(int a, int b) {
    return (a < b) ? a : b;
}
 
int Recovery() {   // 감시처리 전의 상태로 복구함과 동시에 사각지역 탐색 
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tmp[i][j] == 0) cnt++;
            tmp[i][j] = Orign[i][j];
        }
    }
    return cnt;
}
 
void View_Camera(int num, int flag) {  // 몇번 카메라가 몇도 회전 했는지 Prameter로 받는다. 
    int x = v[num].first;  int y = v[num].second;
    for (int i = 0; i < 4; i++) {
        if (Map[x][y][i]) {
            int nx = x + dx[(i + flag) % 4];  int ny = y + dy[(i + flag) % 4];
            while (tmp[nx][ny] != 6 && nx >= 0 && nx < n && ny >= 0 && ny < m) { // 범위를 벗어나지 않거나 이미 감시한 지역(9)이고, 빈칸일경우 
                if (tmp[nx][ny] == 0) tmp[nx][ny] = 9;
                nx += dx[(i + flag) % 4];  ny += dy[(i + flag) % 4];
            }
        }
    }
    return;
}
 
void dfs(int cnt) {
    if (cnt == v.size()) { // 카메라에 대한 회전 정보가 카메라 갯수와 같아젔다면
        for (int i = 0; i < Rotate.size(); i++) // 회전정보만큼 카메라 돌려서 감시지역 처리해주기
            View_Camera(i, Rotate[i]);
        ans = Min(ans, Recovery());
        return;
    }
    for (int i = 0; i < 4; i++) { // 0: No rotate 1: 90  2: 180 3: 270
        Rotate.push_back(i);
        dfs(cnt + 1);
        Rotate.pop_back();
    }
    return;
}
 
int main() {
    cin >> n >> m;   // n = row  ,    m = col 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tmp[i][j];
            Orign[i][j] = tmp[i][j];
            if (!tmp[i][j] || tmp[i][j] == 6)     continue; // 0이나 벽일경우 
            v.push_back(make_pair(i, j));  // Camera Direction (row, col); 
            switch (tmp[i][j]) {  // No1 ~ No5 Camera Direction input
            case 1: // 1type Camera   --> 초기 방향에 대한 정보를 저장해둔다 
                Map[i][j][1] = true;
                break;
            case 2:    //2type Camera
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 3:  // 3type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                break;
            case 4:   // 4type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 5:
                for (int a = 0; a < 4; a++)
                    Map[i][j][a] = true;
                break;
            }
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}


저작자표시

'PS) BOJ > DFS' 카테고리의 다른 글

[C++] 사다리조작 [백준 15684]  (0) 2018.08.15

개인적으로 '감시' 문제보다 구현할게 많지 않아서 간단하게 풀수 있는 문제입니다.  

먼저 '연구소'라는 문제를 풀어본사람은 비슷하다는 느낌을 많이 받았을 것입니다.  

먼저 사다리의 시작점-도착점이 일치하는지 여부를 판별하기전에 사다리부터 놓아야합니다.  

문제 해결 절차 

1. 사다리를 h*n인덱스를 탐색하며 양사이드 [h][n-1]과 [h][n+1], [h][n]이 비어있는 사다리인지 확인 
   해본다. (h가 세로선이므로 행 n이 가로선 번호이므로 열이다.헷갈리지 않게 주의하자) 
2. 비어있다면 사다리를 놓고 재귀호출~ 그리고 재귀호출 끝나고 돌아오면 백트래킹으로 다시 사다리를 
    없애주도록 하자. 생각보다 복잡도가 심하지 않은 편이다. (양사이드와 현재 인덱스가 있으므로 )
 시간을 최대한 줄이자
- 가지치기를 잘하여 사다리들이 시작점으로 모두 도착하는경우 더이상 탐색하지 않는다. 
- 탐색과정에서 행단위로 양사이드 및 해당 열에 사다리를 모두 놓았다면, 해당 행 이상인 부분만 탐색. 

위 조건만 잘 만족시켜준다면 시간안에는 통과할수 있을 것이다. 




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

<Code>


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
// Minerba
#include<iostream>
using namespace std;
bool a[31][11]; int n, m, h, Ladder;    bool res;
bool Count_Ladder() {
    for (int i = 1; i <= n; i++) { // 세로선 번호  // i는 반복문 시작전 최초의 시작점, pt는 변경될 시작점
        int pt = i;
        for (int j = 1; j <= h; j++) {
            if (a[j][pt]) pt += 1;   // 오른쪽으로 이동
            else if (pt - 1 > 0 && a[j][pt - 1]) pt -= 1; // 왼쪽으로 이동 
        }
        if (i == pt) continue;
        else
            return false;
    }
    res = true; 
    return true;
}
 
void dfs(int x, int cnt) {
    if (res) return;
    if (cnt == Ladder) {
        if (Count_Ladder())  m = cnt;
        return;
    }
    for (int i = x; i <= h; i++) {   // 기존 행에 사다리를 놓았다면 해당 행과 같거나 더 커야한다.
                                     // 사다리가 역주행해서 위로 올라갈순 없으니...
        for (int j = 1; j < n; j++) {
            if (!a[i][j]) {
                if (!a[i][j - 1] && !a[i][j + 1]) { // 연속되지 않은 가로선 
                    a[i][j] = 1;
                    dfs(i, cnt + 1);
                    a[i][j] = 0;
                }
            }
        }
    }
    return;
}
 
int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> h;
    while (m--) {
        int x, y; cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 0; i <= 3; i++) {
        Ladder = i;
        dfs(1, 0);
        if (res) break;
    }
    if (!res) cout << -1 << '\n';
    else cout << m << '\n';
    return 0;
}














'PS) BOJ > DFS' 카테고리의 다른 글

[C++]감시[백준 15683]  (0) 2018.08.15

+ Recent posts

티스토리툴바