본문 바로가기
Programming/Algorithm

백준 달이 차오른다 가자

by OKOK 2018. 4. 4.

1. 비트마스킹을 사용합니다.

2. 키를 겟하면, 겟했다고 표기합니다.

3. 문을 만나면 키를 겟했는지 확인합니다. 


특이점

배열큐를 사용할때 크기가 사이즈의 4배를 해주었습니다.

1. stl 큐의 장점은 큐가 동적할당 되는 것인데

2. 배열 큐의 장점은 디버깅시 내용을 바로바로 확인 할 수 있다는 점입니다.

3. 문자열이므로 문자열로 받고, 입력도 문자열로 받습니다. 디버깅 때 알아보기 편합니다.


설계시에, 큐 내용을 알 필요가 없으면, stl? no 디버깅시 유리하도록 front, rear 쓰는 것이 좋을 것 같습니다.


 



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
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define SIZE 51
#define qSIZE 160
char map[SIZE][SIZE];
int visit[SIZE][SIZE][1 << 7];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };int n, m, stx, sty;
 
struct point {
    int x, y, k;
}queArr[qSIZE * qSIZE];
queue<point> que;
int x, y, k;
int nx, ny, nk;
int front, rear;
 
 
int bfs() {
 
    front = rear = -1;
    visit[stx][sty][0] = 1;
    
//    que.push({ stx,sty,0 });
    rear++;
    queArr[rear].x = stx;
    queArr[rear].y = sty;
    queArr[rear].k = 0;
 
//    while(!que.empty()){
    while (rear != front) {
 
//        x = que.front().x;
//        y = que.front().y;
//        k = que.front().k;
//        que.pop();
 
        front++;
        x = queArr[front].x;
        y = queArr[front].y;
        k = queArr[front].k;
 
 
        if (map[x][y] == '1') return visit[x][y][k] - 1;
 
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
 
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == '#' || visit[nx][ny][k] != 0) continue;
            if ('a' <= map[nx][ny] && map[nx][ny] <= 'f') {
                nk = k | (1 << (map[nx][ny] - 'a'));
                if (visit[nx][ny][nk] == 0) {
                    visit[nx][ny][nk] = visit[x][y][k] + 1;
                    
//                    que.push({ nx,ny,nk });
                    rear++;
                    queArr[rear].x = nx;
                    queArr[rear].y = ny;
                    queArr[rear].k = nk;
                }
            }
            else if ('A' <= map[nx][ny] && map[nx][ny] <= 'F') {
                nk = k&(1 << map[nx][ny] - 'A');
                if (nk != 0) {
                    visit[nx][ny][k] = visit[x][y][k] + 1;
                    
                    
                    //que.push({ nx,ny,k });
                    rear++;
                    queArr[rear].x = nx;
                    queArr[rear].y = ny;
                    queArr[rear].k = k;
                }
            }
            else if (visit[nx][ny][k] == 0) {
                visit[nx][ny][k] = visit[x][y][k] + 1;
                
                //que.push({ nx,ny,k });
                
                rear++;
                queArr[rear].x = nx;
                queArr[rear].y = ny;
                queArr[rear].k = k;
            }
        }
    }
 
    return -1;
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
        for (int j = 0; j < m; j++) {
            if (map[i][j] == '0') {
                stx = i;
                sty = j;
            }
        }
    }
    cout << bfs() << endl;
}
cs

 


저작자표시

관련글

티스토리툴바