그냥 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




컴퓨터 N를 최소의 비용으로 연결하기 위해서는 사이클이 생성되도록 연결하면 번복된 연결이 발생하므로 

사이클이 발생하지 않도록 모든 컴퓨터들이 연결되도록 하는 문제로 이해했다. 

입력 -> 정점 V1, V2 가중치 W로  vector에  적재하여 가중치 w를 기준으로 오름차순 정렬을 한뒤에 

Disjoint_Set을 사용하여 사이클 발생여부를 판단하면서 가중치를 더해주면 끝

Disjoint_Set이나 Mst를 숙지하고 있다면 굉장히*3  쉽게 풀수 있는 문제입니다.


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






<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
// pda_pro12
#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 0x7fff0000
#define N_ 100000
using namespace std; 
 
int n, m, par[N_], ans; 
vector<pair<int, pair<int, int>>> v; 
 
int find(int x) {
    if (x == par[x])
        return x; 
    return par[x] = find(par[x]); 
}
 
bool Merge(int x, int y) {
    x = find(x); 
    y = find(y); 
    if (x == y)
        return false; 
    par[y] = x; 
    return true; 
}
 
int main() {
    int v1, v2, w;
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);   
 
    cin >> n >> m; 
    for (int i = 1; i <= n; i++)
        par[i] = i; 
    
    while (m--) {
        cin >> v1 >> v2 >> w; 
        v.push_back({ w, {v1, v2}}); 
    }
    sort(v.begin(), v.end());    // 가중치 별 정렬 
    
    for (int i = 0; i < v.size(); i++) {
        int w = v[i].first; 
        int v1 = v[i].second.first; 
        int v2 = v[i].second.second; 
        if (Merge(v1, v2))  // 사이클 발생하지 않을경우 연결 후  
            ans += w;    // 연결비용 적재 
    }
    cout << ans; 
    return 0; 
}


저작자표시

  




3개월전쯤이었나 이분탐색 문제들중에서 유일하게 못풀었던 문제였다. 


그냥 못풀겠거니~ 하고 냅뒀는데 북마크 문제 뒤적이다가 한번 볼까하고 풀었는데 

인덱스 카운팅을 통해 풀수 있을것 같았다.


-> 석순은 최대 높이부터 아래로 탐색하면서 보다 높은 높이에서 뚫어야할 석순이 있다면 그것보다 낮은 높이에도 뚫어야할게 있는것이므로 1높은 높이에서의 정보를 그대로 가저옴으로서 (종유석도 마찬가지) 종유석과 석순에 대한 뚫어야할 갯수 정보를 저장한다. 

갱신된 석순과 종유석을 기반으로 높이 하나하나(1~ h)까지의 관점에서 종유석과 석순의 뚤어야할 갯수를 더하며 정해를 찾아낸다.





<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
// pda_pro12
#include<iostream>
 
#define N_ 500001
#define D 0x7fffffff
 
using namespace std;
 
int s[N_], r[N_], s_b[N_], s_t[N_], n, h, min_ = D, cnt_; 
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL), cout.tie(NULL); 
    cin >> n >> h; 
    for (int i = 0; i < n / 2; i++) {
        int t, b; 
        cin >> b >> t; 
        s_b[b]++; s_t[t]++; 
    }
    for (int i = h; i >= 1; i--) {   // 가장 높은 높이부터 
        s[i] = s_b[i] + s[i + 1]; s_b[i] = 0; 
        r[i] = s_t[i] + r[i + 1]; 
    }
    for (int i = 1; i <= h; i++) {
        s_b[i] = s[i] + r[h - i + 1]; 
        if (s_b[i] <= min_)
            (s_b[i] == min_) ? cnt_++ : cnt_ = 1, min_ = s_b[i]; 
    }
    cout << min_ << ' ' << cnt_; 
    return 0;
}


저작자표시


문제 설명에서 가장 먼거리에 숨은 헛간의 번호를 찾는다고 하였으나 사실상 시작점으로 부터
각 헛간까지 우회하는 경로가 없어야하므로, 다익스트라로 각 헛간까지의 최단거리를 
갱신해주면된다. 

중요한것은 거리를 기준으로 정렬하였을때, 초기 입력받은 번호에 대한 정보를 잃지 않기 위해서 

구조체 형식으로 거리배열을 생성하고, 갱신하였다. 

나머지는 무방향 그래프이면서 최대거리와 최대거리 요소의 갯수만 찾아주면 간단히 해결된다.



<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
//pda_pro12
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
 
#define all(x) x.begin(), x.end()
#define INT 0x7fffffff
#define N_ 20001
 
using namespace std;
 
struct DATA { int num, value; };
 
vector<pair<int, int>> v[N_]; priority_queue<pair<int, int>> pq;
int n, m; DATA dst[N_]; int x, y; vector<int> ans;
 
bool cmp(DATA u, DATA t) {
    return u.value < t.value;
}
bool cmp1(DATA u, DATA t) {
    return u.num < t.num;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    while (m--) {
        cin >> x >> y;
        v[x].push_back({ y, 1 });
        v[y].push_back({ x, 1 });
    }
    for (int i = 1; i <= n; i++) {
        dst[i].value = INT, dst[i].num = i;
    }
    dst[1].value = 0;
    pq.push({ 1, 0 });
    while (!pq.empty()) {
        int v_x = pq.top().first;
        int dis = -pq.top().second;
        pq.pop();
        if (dis > dst[v_x].value) continue;
        for (int i = 0; i < v[v_x].size(); i++) {
            int next = v[v_x][i].first;
            int n_dis = dis + v[v_x][i].second;
            if (n_dis < dst[next].value) {
                dst[next].value = n_dis;
                pq.push({ next, -n_dis });
            }
        }
    }
    sort(dst + 1, dst + 1 + n, cmp);
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        if (Max < dst[i].value) {
            Max = dst[i].value;
            ans.clear();
            ans.push_back(dst[i].num);
        }
        else if (Max == dst[i].value)
            ans.push_back(dst[i].num);
    }
    sort(all(ans));
    cout << ans.front() << ' ' << Max << ' ' << ans.size();
 
    return 0;
}


저작자표시

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

[C++]알고스팟[백준1261]  (0) 2018.08.15





처음엔 A....뭐야... 그냥 bfs로 슥삭하면되겠네....

라고 생각했지만 아니었다. 

더 많은 칸을 가야하지만 최소의 벽을 깨고 가는 경우가 있기 때문이었다. 

기냥 2차원 거리 배열을 선언해서 INF로 초기화해주자. 

어차피 시작점은 0,0 이니 거리배열 [0][0] = 0으로 해주자 

똑같이 Priority_Queue를 사용하는데 인자로 <int,int> int를 주었다. 

Vertext 하나의 위치정보가 x,y좌표이므로 ~
간선정보는 배열자체에 주어져있으므로 필요없고, 연결 노드야 현시점에서 4방향

탐색을 통한 지점일테고....

다만 시간줄이려고 cin.tie(NULL)해놓고 scanf를 써서 맞왜틀을 30분 겪었다...ㅎㅎ

나머지는 단순한 다익스트라로 쉽게 풀린답


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



<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
// pda_pro12
#include<algorithm>
#include<queue>
#include<iostream>
 
#define lng(x) x.length()
#define sz(x) x.size()
#define N_ 101
#define INT 0x7fffffff
using namespace std;
 
int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,-1,1 };
int n, m, a[N_][N_], dst[N_][N_];
priority_queue<pair<pair<int, int>, int>> pq; 
 
int main() {
    cin >> n >> m; 
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%1d", &a[i][j]),dst[i][j] = INT; 
    dst[0][0] = 0;
    pq.push({ {0,0},0 }); 
    while (!pq.empty()) {
        int v_x = pq.top().first.first; int v_y = pq.top().first.second; 
        int dis = -pq.top().second;
        pq.pop(); 
        if (dis > dst[v_x][v_y]) continue; 
        for (int i = 0; i < 4; i++) {
            int nx_x = v_x + dx[i]; int ny_y = v_y + dy[i]; 
            if (nx_x < 0 || nx_x >= m || ny_y < 0 || ny_y >= n) continue; 
            int n_dis = dis + a[nx_x][ny_y]; 
            if (n_dis < dst[nx_x][ny_y]) {
                dst[nx_x][ny_y] = n_dis; 
                pq.push({ {nx_x, ny_y}, -n_dis }); 
            }
        }
    }
    cout << dst[m - 1][n - 1]; 
    return 0;
}


저작자표시

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

[C++]숨바꼭질[백준 6118]  (0) 2018.08.15








입국심사대 N이 10만,   입국 처리인원이 10억으로 Max값이 주어진다. 각 심사대에서 처리하는데 소요되는 시간 또한 10억이다. 완탐으로 1초안에 해결이 불가능한 문제이다. 
이걸 완탐돌린다면... 생각만 해도 끔찍하다. 

착안해낸 아이디어
1. 하한값을 1로 잡고 상한값을 10억*10만값으로 가정하고 풀이하였다.
    (WorstCase: 각 심사대10억*10만)

2.  이분탐색으로 시간을 가정하고 해당 시간으로 10만의 심사대에서 처리하고자하는 인원 M을 처리할
     수 있는지 혹은 처리하기에 시간이 부족한지를 살펴본다. 

3. 처리시간이 부족하다면 하한을 중간값+1로 설정하여 중간값을 다시 설정하고 이분탐색을 진행한다. 
    인원처리가 가능하다면 상한값을 중간값-1로 설정하여 left값이 right를 초과하는 순간 종료된다. 

4. lft는 항상 최소한의 가능한순간까지의 하한값을 증가시킬것이다. right값을 lft값이 초과하는 순간
   빠져나와버리므로 수용가능한 경우의 최소 mid값과 lft값은 일치한다. 
시간 복잡도 :  O(NlogN) 
탐색과정을 보면 다음과 같다 





<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
// pda_pro12
#include<iostream>
#include<algorithm>
#define N_ 100000
#define Upper 100000000000000   // N_ * M(max)
 
using namespace std;
 
typedef long long ll;
ll lft, rgt, n, m;   int a[N_];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        cin >> a[i];
 
    ll lft = 1;  ll rgt = Upper;   // Lower ,  Upper
 
    while (lft <= rgt) {
        
        ll mid = (lft + rgt) >> 1;
        ll Sum = 0;
        for (int i = 0; i < n; i++)
            Sum += (mid / a[i]);
        if (Sum >= m)
            rgt = mid - 1; 
        else
            lft = mid+1;
    }
    cout << lft << '\n';
    return 0;
}


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

[C++]수열 걷기[백준 4929]  (0) 2018.08.21
[C++] 랜선 자르기 [BOJ 1654]  (0) 2018.08.16
[C++] K번째 수[백준 1300]  (0) 2018.08.16
[C++] 게임 [백준 1072]  (0) 2018.08.16

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

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

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

문제 해결 절차 

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




※문제 해결 과정

A, B, C물통이 있고 초기에 C만 꽉차있다. 여기서 물통의 물이 옮겨지는 경우의 수를 BFS로 물통들의 

잔량을 큐에 저장하면서 돌려주면 된다. 



먼저 C->A물통으로 옮기는경우와 C->B물통으로 옮기는 경우가 있다. 

또 B->C물통으로 옮기는 경우와 B-> A물통으로 옮기는 경우

A->C물통으로 옮기는 경우, A->B물통으로 옮기는 경우를 따져주면 된다. 중요한건 A물통의 잔량이 

비었다면 그때의 C물통에 있을 수있는 물의 양이므로 물을 옮기는 과정에서 A물통의 잔량이 없다면 

물의 양이 1~200까지 밖에 주어지지 않으므로 그때의 Array_[C의 잔량] = true; 이런식으로 체크해주

면된다. 여기서 방문처리와 같은 배열처럼 같은 물의 양 조합이 또나오면 번복하는 연산이 일어날수 있

으므로  A,B물통의 잔량을 이차원배열로 체크를 해준다. Array_[A잔량][B잔량] = true; 



(물통이 2개라서 이런식으로 체크가 가능한것이다..ㅠ) 



다돌려주고 나서 1~200까지 쭉 올라가면서 체크된 c의 잔량 배열을 출력해주면 


AC를 받을수 있을 것이다. 



<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
//pda_pro12
#include<algorithm>
#include<iostream>
#include<queue>
 
using namespace std;
 
bool chk[201][201];  // a, b 물통의 물의 양을 확인해주는 배열
bool ans[201];   // c물통의 물의 양을 확인해주는 배열 
int a, b, c, sum;
 
queue<pair<int, int>> q;
 
int main() {
    cin >> a >> b >> c;
    chk[0][0] = true;
    ans[c] = true;
    sum = c;   // c물통에만 가득차있으므로 손실되는 물이 없으면 총량은 c의 들이와 같음
    q.push(make_pair(0, 0));
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        int z = sum - (x + y);   // 
        q.pop();
        int nx, ny, nz;
        nx = x; ny = y; nz = z;
        ny += nx;
        nx = 0;
        if (ny >= b) {  // 물의 이동시 살펴줘야할 조건 
            nx = ny - b;
            ny = b;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
        nx = x; ny = y; nz = z;
        nz += nx;
        nx = 0;
        if (nz >= c) {
            nx = nz - c;
            nz = c;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
        nx = x; ny = y; nz = z;
        nz += ny;
        ny = 0;
        if (nz >= c) {
            ny = nz - c;
            nz = c;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
 
        nx = x; ny = y; nz = z;
        nx += ny;
        ny = 0;
        if (nx >= a) {
            ny = nx - a;
            nx = a;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
 
        nx = x; ny = y; nz = z;
        ny += nz;
        nz = 0;
        if (ny >= b) {
            nz = ny - b;
            ny = b;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
        nx = x; ny = y; nz = z;
        nx += nz;
        nz = 0;
        if (nx >= a) {
            nz = nx - a;
            nx = a;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
    }
    for (int i = 0; i <= c; i++) {
        if (ans[i]) {
            cout << i << ' ';
        }
    }
    return 0;
}


+ Recent posts

티스토리툴바