인덱스 범위가 10만이고 인덱스마다 값의 범위는 -100~100인 배열을 입력으로 주고, 

구간을 갱신, 합산출을 M만큼 해주는건데 K의 범위또한 10만이다. 

(즉, -> Prefix_Sum을 사용하거나 세그먼트를 써야한다는건데 갱신이 있으므로 세그먼트를 썻다.)

시간복잡도는 대략 O(KlogN) 인것 같다. 

구현한 세그먼트는 바텀-업 세그먼트를 사용하였다

처음 풀때 실수 했던게 10만개의 인덱스가 전부 100을 갖고 있을때는 곱셈연산이므로 

100의 10만승이라는 1Googol을 훌쩍 넘어버리는.. 수가 발생한다는 것을 뒤늦게 알고, 

( 참고로 1구골이  10의 100승이다 ) 


세그트리를 구축해주는 함수에서 음, 양, 0을 판별하고 부분곱 방식으로 트리를 쌓아올렸다. 

스티커 이미지

그래도 실행시간은 나쁘지 않게 나와서 좀 만족스럽다 ㅎㅎㅎ

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

5676번: 음주 코딩
문제 오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다. 상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다. 먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X 1 , X 2 , ... X N 을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다. 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다. 곱셈: 선영이는 상근이에게 i와 j를
www.acmicpc.net


<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
// pda_pro12
#include<algorithm>
#include<iostream>
#define N_ 100001   // 수열의 최대 크기 
#define INT 0x7fff0000
 
using namespace std; 
 
typedef long long ll; 
int seg[N_ * 4], a[N_], t, n, m, k;
 
void init(int node, int x, int y) {
    if (x == y) {
        if (a[x] > 0) seg[node] = 1; 
        else if (a[x] == 0) seg[node] = 0; 
        else if (a[x] < 0)  seg[node] = -1; 
        return; 
    }
    int mid = (x + y) >> 1; 
    init(node << 1, x, mid); 
    init((node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] * (seg[(node << 1) + 1]); 
    return; 
}
 
void update(int pos, int val, int node, int x, int y) { 
    if (pos < x || pos > y) return; 
    if (x == y) {
        if (val > 0) seg[node] = 1;
        else if (!val) seg[node] = 0; 
        else if (val < 0) seg[node] = -1; 
        return; 
    }
    int mid = (x + y) >> 1; 
    update(pos, val, node << 1, x, mid); 
    update(pos, val, (node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] * seg[(node << 1) + 1]; 
    return; 
}
 
int query(int lo, int hi, int node, int x, int y) {
    if (lo > y || x > hi) return 1; 
    if (lo <= x && y <= hi) return seg[node]; 
    int mid = (x + y) >> 1; 
    int l = query(lo, hi, node << 1, x, mid); 
    int r = query(lo, hi, (node << 1) + 1, mid + 1, y); 
    return l*r; 
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
    
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++)
            cin >> a[i]; 
 
        init(1, 1, n); 
        while (m--) {
            char inp; int x, y; 
            cin >> inp >> x >> y;
            if (inp == 'C') 
                update(x, y, 1, 1, n);
            else if (inp == 'P'){
                int ans = query(x, y, 1, 1, n);
                if (ans == 0)
                    cout << '0';
                else if (ans > 0)
                    cout << '+';
                else if ( ans < 0)
                    cout << '-'; 
            }
        }
        cout << '\n'; 
    }
    return 0; 
}


저작자표시

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

[C++] 커피숍2 [백준 1275]  (0) 2018.08.17
[C++] 커피숍2 [백준 1275]  (0) 2018.08.16

이 포스팅을 보고 많은분들이 LIS에 대해서 아! 하시고 창을 닫으시길 바라며 

포스팅을 해보겠습니다. 

물론 제가 올린 내용중 문제가 되는 부분이 있다면 언제든지 댓글로 남겨주시면 환영입니다!
( 필자는 아직 좁밥이므로 갓들의 지적속에 자라나고 있습니다 )

n사이즈의 배열에서 일부 원소들을 뽑아내어 부분수열을 만들어 내었을때 

증가하는 수열이 되도록 할때, 가장 긴 길이를 구하는 문제를 LIS라고 합니다. 

Dynamic Programming에서 빈번하게 등장하는 문제로 알고있으며 실제로 감소하는 수열도 존재합니다.

예를 들어 [5, 2, 3, 7, 4, 1] 이라는 배열이 있다고 해보겠습니다. 

먼저 이 배열에서 가장 긴 증가하는 부분수열을 뽑아낸다고 한다면, [2, 3, 4,]를 뽑아낸

길이 3이 LIS의 길이가 됩니다. 

문제에 대한 설명에 앞서 

인덱스 트리 풀이법, N^2풀이법,  lower_bound 풀이법 등 다양한 방법이 존재하지만 필자가 알고있는 

N^2 풀이법과 Lower_bound를 사용한 선형시간으로 푸는 방법에 대하여 설명하도록 하겠습니다. 


그렇다면 N^2의 풀이를 먼저 사용하여 

풀이해보겠습니다.

1. N^2을 사용해보자
N^2을 사용하기 위해서는 일반적으로 N사이즈가 1000 정도에서 빈번하게 사용되고 있습니다. 
그렇다면 N^2의 풀이는 어떤 풀이길래????? 

원본 배열 arr[]


위와 같은 수열이 있다고 생각해보자
 
원본배열 arr[]에 위 값들을 저장해두고 

입력과 동시에 자기자신은 길이 1을 가지고 있으므로

원본과 같은사이즈의 배열 dp[i] (value가 있는 index번째에) 1로 초기화 해주도록 하자 

lis 길이저장 배열 dp[]

자 그러면 이제 원본의 1번째부터 n번째까지 핀을 꽂으면서 그 앞쪽을 탐색해본다고 따저보자 
이게 이해가 되지 않는다면 아래 그림을 참고해보자 

핀을 꽂은 위치를 기준으로 앞쪽을 전부 탐색해보는것이다. 이짓을 왜하냐?
왜냐하면 핀을 꽂은 위치가 자신보다 앞쪽 인덱스에 위치한 value가 작다면, 즉 (증가수열을 이룰수도 있는 부분이라면!)
-> 내가 앞쪽에 있는 값보다 크다면 당연히 증가수열이지 않은가 

그렇다면 해당 인덱스에 저장된 DP테이블값을 보는것이다! 

즉, dp테이블에 저장된 데이터의 의미는 엄밀히 말하면  

(i번째까지 핀을 꽂으면서 탐색을 해보았을 때 가장 긴 LIS의 길이만 저장되어있는것이다.)
(가장 중요한건 i번째까지만!!! 계산했을때이다. )

위그림은 핀을 꽂은 순서에 따라서 DP테이블에 저장된 LIS의 길이를 저장한것이다. 이 테이블 내의 값과 과정이 이해가 된다면
N^2에 대한 이해는 완벽히 되었다고 볼수 있다. 

이제  지금까지 설명해본 논리를 종합해보자
1. 원본을 기준으로 DP테이블을 갱신해 나간다고 생각하는것이 바탕되어있다. 

2. 원본 1번째부터 N번째까지 그 앞쪽의 인덱스들을 무식하게 전부 봐주는 방식인데
            원본 현 인덱스보다 작다면(증가수열이 가능하므로) 해당 인덱스의 DP테이블에 
저장된VALUE+1을했을때 기존에 저장되어있던 값보다 크다면 
갱신해주고 아니라면 SKIP해준다.

3. 그럼 이제 그 과정에서 즉 항상 맨마지막 인덱스가 LIS값이 저장되어있다는 보장이 없으므로 
매번 기준이 되는 원본 인덱스에서의 DP값들 중의 최대값이 LIS이므로 
max값만 갱신해주며 쭉 끝까지 탐색하면 된다~


자 이제 Lower_bound를 활용한 좀더 큰 사이즈의 배열의 LIS를 구해보자

이 풀이는 선형시간, 즉 O(n)으로 해결할 수 있는 풀이이다. 그렇다면 O(n)으로 어떻게 해결할 수 있나?
Lower_bound (이분탐색 기반의 해당 value 이상의 값이 최초로 등장하는 인덱스의 위치를 찾아내는 알고리즘이다)
을 사용하여 value 이상이 등장하는 위치를 찾아준다. 

먼저 위와 같은 똑같은 원본배열로 설명하겠다.

int arr[]

준비물은 정수형 벡터 하나와 lower_bound 알고리즘이면 된다. 

vector<int>

자 그렇다면 먼저 vector안에 -1을 넣고 시작한다. 
물론 lis 문제가 자연수 문제일경우에만 해당된다. 

(어떠한 수가와도 본인자체의 길이는 1이 되므로 )
여기서는 vector 컨테이너에 한번 넣을수 있다는 것이 어떠한 Event라고 생각해주면된다. 

즉 vector에 보관되고 있는 수들은 기존에 갱신해왔던 lis길이를 구성하였었던 수들? 이라고 말하면 편하겠다. 
그치만 lis가 3일때의 ->  vector<int>에는 딱 이수들이 있어야겠지? 라는 말이 아니다.

위 그림을 가지고 과정을 설명해보겠다. 

----------------------------------------------------<1 stage>----------------------------------------------------

----------------------------------------------------<2 stage>----------------------------------------------------

----------------------------------------------------<3 stage>----------------------------------------------------

이 단계에서 어떤 로직이 일어날까? 그렇다 Lower_bound알고리즘을 사용하여 
현 vector컨테이너에 저장된 수들(현존하는 lis 구성 체제라고 보는게 맞을것 같다 )

여기서 이 원본의 작은 수가 현 vector컨테이너에 들어왔을때 (어느 계급??)인지를 

보는게 맞을것같다. 
이때 사용되는 Lower_bound알고리즘의 복잡도는 O(LogN)이다
즉!!! 뒤에 등장한 작은수가 더 긴 lis수로 거듭날수 있는지 현체제의 해당 계급의 수와 1대1 매칭시켜가줘보는것이다.

( 사실 위에서 한말이 이 알고리즘 설명의 전부인것 같다 ) 
그렇다면 계속해서 구해보자. ( 이해가 안될땐 의심이 많아지기 때문이다 )

----------------------------------------------------<4 stage>----------------------------------------------------

짜잔~ 이렇게 바뀌엇다. 

그럼이제 계속 더 잘 진행해보자

---------------------------------------------------- <5 stage> ---------------------------------------------------- 

---------------------------------------------------- <6 stage> ---------------------------------------------------- 

---------------------------------------------------- <7 stage> ---------------------------------------------------- 

여기서는 이제 기존에 구성되어있던 LIS 만큼의 수들이 새롭게 등장한 back보다 작은 수들로 바뀌어 back마저(비교 대상마저 바뀐 상태이다)

---------------------------------------------------- <8 stage> ---------------------------------------------------- 

갱신된 back을 기준으로 원본가 비교가 이루어지는 상태이다

---------------------------------------------------- <9 stage> ---------------------------------------------------- 


자 이렇게 하면 이제 count: 5를 마지막으로 종료가 되엇다. 

저뒤에 어떠한 5나 6아 온다고 한들 back보다 작으므로 현수열의 back이 갱신될때까지의 인덱스는 기존 벡터

에도  5나 6이 잔존하니 길이가 갱신될리가 없는것은 자명하다. 

파란색으로 칠한 인덱스는 Lower_bound를 통해 갱신된 것을 표시한것이다. 

총 lower_bound함수호출 3번, 탐색은 1방향으로 O(N)이 이루어졌다. 
즉 NLogN정도?의 복잡도가 발생하는것 같다

< 연습 문제 >
https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열
11053번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 가장 긴 증가하는 부분 수열 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 20796 7600 5235 37.489% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10 , 20 , 10, 30 , 20, 50 }
www.acmicpc.net

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

12015번: 가장 긴 증가하는 부분 수열 2
12015번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 가장 긴 증가하는 부분 수열 2 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 512 MB 2712 1102 777 44.173% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10 ,  20 , 10,  30
www.acmicpc.net
<Code> - (n제곱 풀이법)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//2018年 08月 15日 LIS 
//pda_pro12
#include<iostream>
#include<algorithm>
#define N_ 1001
using namespace std;
int dp[N_], a[N_], n, m, ans;
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL), cout.tie(NULL); 
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> a[i], dp[i] = 1;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[i] > a[j]) 
                dp[i] = max(dp[i], dp[j] + 1);
            ans = max(ans, dp[i]); 
        }
    }
    cout << dp[n];
    return 0;
}

<Code> - (Lower_bound 풀이법)


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
//2018年 08月 15日  LIS 
//pda_pro12
#include<iostream>
#include<algorithm>
#include<vector>
 
#define N 1000001
#pragma warning(disable:4996)
 
using namespace std; 
 
int n, m, a[N], ans; vector<int> v(n); 
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL), cout.tie(NULL); 
 
    cin >> n; 
    for (int i = 1; i <= n; i++)
        cin >> a[i]; 
    v.push_back(-1); 
    for (int i = 1; i <= n; i++) {
        if (v.back() < a[i]) {
            ans++;     // ans가 counting 해주는 것은 back을 갱신하는 순간이 몇번이엇는지 (즉 현재까지 세어온 LIS의 길이를 갱신해주었던 순간의 횟수를 세어주는 것이다 )
            v.push_back(a[i]);
        }
        else {
            auto j = lower_bound(v.begin(), v.end(), a[i]); // a[i]이상의 값이 등장하기 시작하는 인덱스의 위치를 찾는다
            *j = a[i];      // a[i]로 해당 lower_bound번째의 인덱스를 수정해주므로 이 값은 이제   
        }
    }
    cout << ans; 
    return 0; 
}


저작자표시

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

+ Recent posts

티스토리툴바