uang's blog

이 문제는 BFS 를 이용해 푸는 미로 문제의 응용버전이라고 볼 수 있다.

이 문제만의 특징은 'A'~'F' 의 문이 있고, 문을 열기 위해선 각 알파벳에 맞는 소문자 'a'~'f' 열쇠를 가지고 있으면 통과할 수 있다.

다행히 문과 열쇠의 종류가 6개 밖에 안되기 때문에, 비트마스크를 이용해 저장할 수 있고

주의할 점은 지나온 길을 다시 가지 않기 위한 visited 변수는 키의 보유 상황에 따라 갈 수 있는 길이 다르기 때문에 이를 고려해야한다.

 소스코드

 풀이 방법

이 문제는 두 지점 사이의 최소 거울 수를 구하는 문제로, 평소 두 지점의 최단거리를 구할 때 사용하는 BFS 를 응용해 "거리" 대신 "거울 수(방향 전환이 일어나는 수)" 를 사용하여 풀 수 있다고 생각했다.

단순 좌표 (y, x) 뿐만 아니라, 사용된 거울 수 및 이동해온 방향 정보가 필요하므로 새로운 구조체를 정의한다.

struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};

이동해온 방향(p_dir)을 저장하는 이유는 거울이 사용되는 지점이 방향이 전환되는 시점이기 때문에, 현재 좌표가 어느 방향에서 왔는지 확인하기 위해 필요하다.

이 구조체를 이용해 사용된 거울 수(num) 이 가장 작은 순으로 queue 에서 가져오기 위해 우선순위 큐를 사용한다.

 우선순위 큐의 Comparator 정의

내가 정의한 구조체에서 max-heap 으로 사용할지  min-heap 으로 사용하지 결정하기 위해 compartor를 정의해야 한다.

방법은 구사과 님의 블로그에 자세히 설명돼있다.

풀이에 사용된 방법은 구조체를 이용해 operator() 를 정의해 사용했다.

struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};

// 중략

priority_queue< cell, vector<cell>, cmp > pq;

* 참고로 greater 는 작은 값을 먼저, less 는 큰 값을 먼저 리턴한다.

* a.num > b.num 는 greater 와 같고, a.num < b.num 은 less 와 같다.

이렇게 정의된 우선순위 큐를 이용하면, 시작지점에서 거울을 사용하지 않고 최대한 이동하여 탐색한 후,

거울  1개, 2개, k개 사용해서 이동할 수 있는 위치를 순차적으로 탐색할 수 있다.

 소스코드

#include<stdio.h>
#include<vector>
#include<queue>
 
using namespace std;
 
struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};
struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};
 
/*
bool operator<(const struct cell a, const strcut cell b){
    return a.num > b.num;
}
*/
int w,h, sy=-1,sx=-1, dy,dx;
int dix[4] = {-1,1,0,0}, diy[4] = {0,0, -1, 1};
char board[111][111];
bool visited[111][111];
bool dir_check(int a, int b){
    return (a<2 && b<2) || (a>=2 && b>=2)  || a == -1;
}
int main(){
    scanf("%d%d",&w,&h);
 
    for(int i=0;i<h;i++){
        scanf("%s", board[i]);
        for(int j=0;j<w;j++){
            if(board[i][j] == 'C'){
                if(sy != -1 && sx != -1){
                    dy = i, dx = j;
                } else {
                    sy = i, sx  = j;
                }
            }
        }
    }
    priority_queue< cell, vector<cell>, cmp > pq;
    // priority_queue< cell, vector<cell>, greater<cell> > pq;
 
    pq.push(cell(sy, sx, 0, -1));
    while(!pq.empty()){
        cell cur = pq.top();
        pq.pop();
        visited[cur.y][cur.x] = 1;
        if(cur.y == dy && cur.x == dx){
            printf("%d\n", cur.num);
            break;
        }
        for(int i=0;i<4;i++){
            int ny = cur.y + diy[i], nx = cur.x + dix[i];
            if(ny >=0 && nx >=0 && nx < w && ny < h) {
                if(!visited[ny][nx] && board[ny][nx] != '*'){
                    // printf("\tnext : (%d, %d) num : %d, is_plus? : %d\n", ny,nx, cur.num, !dir_check(cur.p_dir, i));
                    pq.push(cell(ny, nx, cur.num + (dir_check(cur.p_dir, i) ? 0 : 1), i));
                }
            }
        }
    }
    return 0;
}

"구간 합" 유형 + 값 수정 쿼리 가 있는 문제는 "세그먼트 트리" 를 이용해 풀어야 한다.

구간 합은 보통 prefix sum(psum) 배열을 이용해 [a, b] 의 구간합을 psum[b] - psum[a-1] 로 풀 수 있다.

하지만 구간 값이 변경되는 "K 개의 수정 쿼리"가 있을 때는, 매 수정마다 N 크기의 배열을 다시 계산해야하기 때문에,

전체 복잡도가 O(K*N) 이 된다.

세그먼트 트리는 

     Leaf node      : 배열 값

     Internal node : 자식노드들의 구간 합

을 저장하여, 수정을 O(logN) 만에, 구간 합 계산 또한 O(logN) 번 만에 수행할 수 있는 자료구조이다.

자세한 내용은 백준님 블로그에 설명되어 있다.

이 문제는 값 수정 쿼리가 있는 구간 곱을 계산하는 문제로, 세그먼트 트리를 이용해야하며, 합 대신 곱 연산으로 변경해주면 된다.

#주의할 점

* 곱 연산이기 때문에 발생하는 오버플로우 문제가 있다.

* update 를 하는 방식은 다양하지만, 이전 값과의 차이(difference) 값을 해당 노드마다 곱해주는 방식으로는 WA 를 받는다.

  - difference 값을 계산하면서 발생하는 나눗셈 연산이 문제의 조건인 1000000007 MOD 연산에 영향을 줄 수 있을 것 같다.

  - 따라서 잎 노드의 변경으로부터 다시 계산하는 방식으로 업데이트를 수행한다.

소스코드

1. #include<stdio.h>
2. #include<vector>
3. #define MOD(x) ((x)%1000000007)
4. using namespace std;
5. typedef unsigned long long ull;
6. int n, m, k;
7. ull arr[1000001];
8.  
9. ull make_seg_tree(vector< ull > &v, int node, int start, int end){
10. if(start == end){
11. return v[node] = arr[start];
12. }
13. return v[node] = MOD( make_seg_tree(v, node*2, start, (start+end)/2) *
14. make_seg_tree(v, node*2+1, (start+end)/2 + 1, end));
15. }
16. ull update_seg_tree(vector<ull>&v, int node, int start, int end, int idx, ull val, bool was_zero) {
17. if( idx < start || end < idx) return v[node];
18.  
19. if(start == end) {
20. arr[idx] = val;
21. return v[node] = val;
22. } else {
23. return v[node] = MOD(update_seg_tree(v, node*2, start, (start+end)/2, idx, val, was_zero) *
24. update_seg_tree(v, node*2+1, (start+end)/2+1, end, idx, val, was_zero));
25. }
26. // v[node] = was_zero ? val : MOD((ull)(v[node] / arr[idx] * val)); // difference 를 이용한 수정
27. }
28.  
29. ull get_mul(vector< ull >&v, int node, int start, int end, int left, int right) {
30. if(right < start || end < left) return 1;
31. if(start==end) return v[node];
32. if(left <= start && end <= right){
33. return v[node];
34. }
35. return MOD( get_mul(v, node*2, start, (start+end)/2, left, right) *
36. get_mul(v, node*2+1, (start+end)/2+1, end, left, right));
37. }
38.  
39. int main(){
40. scanf("%d %d %d",&n,&m,&k);
41. for(int i=1;i<=n;i++){
42. scanf("%u",&arr[i]);
43. }
44. vector< ull > v(4*n);
45. make_seg_tree(v, 1, 1, n);
46.  
47. int a, b,c;
48. for(int i=0; i<m+k;i++){
49. scanf("%d %d %d",&a, &b, &c);
50. if(a == 1){
51. //update
52. bool was_zero = arr[b] == 0;
53. ull val = (ull)c;
54. update_seg_tree(v, 1, 1, n, b, val, was_zero);
55. arr[b] = val;
56. } else{
57. //get mul
58. printf("%u\n", get_mul(v, 1, 1, n, b, c));
59. }
60. }
61.  
62. return 0;
63. }