https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH&categoryId=AWIeW7FakkUDFAVH&categoryType=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
#include<iostream>
#include<cmath>
using namespace std;
 
int n, len, map[21][21];
bool used[21][21];
 
bool rowCheck(int i) {
 
    for (int j = 0; j < n-1; j++) {
        if (used[i][j + 1]) continue; //다음 지점에 이미 경사로 있으면
        if (abs(map[i][j] - map[i][j + 1]) >= 2) return false; //2이상 차이
        
        if (map[i][j] == map[i][j + 1] + 1) {
            if (j + len >= n) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = j + 1; k <= j + 1 + len - 2; k++) {
                if (map[i][k] != map[i][k + 1]) return false;
            }
 
            for (int k = j + 1; k <= j + 1 + len - 1; k++) { //이미 경사로가 놓인 경우
                if (used[i][k]) return false;
            }
            
            for (int k = j + 1; k <= j + len; k++) //경사로 표시
                used[i][k] = true;
        }
 
    }
 
    for (int j = 0; j < n-1; j++) {
        if (used[i][j + 1]) continue; //다음 지점에 이미 경사로 있으면
        
        if (map[i][j] == map[i][j + 1] - 1) {
            if (j + 1 - len < 0) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = j + 1 - len; k <= j - 1 ; k++) {
                if (map[i][k] != map[i][k + 1]) return false;
            }
 
            for (int k = j + 1 - len; k <= j; k++) { //이미 경사로가 놓인 경우
                if (used[i][k]) return false;
            }
 
            for (int k = j + 1 - len; k <= j ; k++) //경사로 표시
                used[i][k] = true;
        }
    }
    return true;
}
 
bool colCheck(int j) {
    for (int i = 0; i < n - 1; i++) {
        if (used[i+1][j]) continue; //다음 지점에 이미 경사로 있으면
        if (abs(map[i][j] - map[i+1][j]) >= 2) return false; //2이상 차이
 
        if (map[i][j] == map[i+1][j] + 1) {
            if (i + len >= n) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = i + 1; k <= i + 1 + len - 2; k++) {
                if (map[k][j] != map[k+1][j]) return false;
            }
 
            for (int k = i + 1; k <= i + 1 + len - 1; k++) {
                if (used[k][j]) return false;
            }
 
            for (int k = i + 1; k <= i + len; k++) //경사로 표시
                used[k][j] = true;
        }
 
    }
 
    for (int i = 0; i < n - 1; i++) {
        if (used[i+1][j]) continue; //다음 지점에 이미 경사로 있으면
 
        if (map[i][j] == map[i+1][j] - 1) {
            if (i + 1 - len < 0) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = i + 1 - len; k <= i - 1; k++) {
                if (map[k][j] != map[k+1][j]) return false;
            }
 
            for (int k = i + 1 - len; k <= i; k++) {
                if (used[k][j]) return false;
            }
 
            for (int k = i + 1 - len; k <= i; k++) //경사로 표시
                used[k][j] = true;
        }
    }
 
    return true;
}
 
int process() {
    int ret = 0; //활주로로 사용가능한 길
 
    for (int i = 0; i < n; i++) {
        if (!rowCheck(i)) //가로방향 확인
            continue;
        ret++;
    }
 
    //경사로 초기화
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            used[i][j] = false;
 
 
    for (int j = 0; j < n; j++) {
        if (!colCheck(j)) 
            continue;
        ret++;
    }
    
    return ret;
}
 
int main(void) {
    //setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
    
    for (int t = 1; t <= T; t++) {
        cin >> n >> len;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        int res = process();
 
        cout << "#" << t << ' ' << res << '\n';
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map[i][j] = 0;
 
        //경사로 초기화
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                used[i][j] = false;
 
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16
SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15
SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu



대각선으로 좌표를 이동하도록 DFS를 구현해주면 된다.



그래프 문제를 풀이할 때 접해봤던 유형으로, 노드에서 사용되었던 숫자를 다시 사용하지 않으면서, 출발지점으로 되돌아가는 데에 필요한 이동 횟수를 구해주면 된다.


이 문제에서는 그러한 경우의 최솟값을 구해주면 되겠다.


그리고 사각형을 이루어야 한다는 것을 생각해서 구현해주면 되겟다.


이 부분은 코드의 주석으로 확인할 수 있다.



DFS를 진행할 때, 일반적으로 방문했던 지점은 다시 방문하지 않도록 처리한다. 또한, 이 문제의 경우, 시작지점에서 사용했던 숫자는 무조건 사용했다는 처리가 되어있기 때문에, 이미 사용했던 숫자라고 하더라도, 그 지점이 시작 지점일 경우 함수 진입을 허용해주도록 구현해야 한다.



본인은 구현을 하다보니, 시작 지점을 방문처리 하지 않고 시작한 이후에, 다음 목적지가 출발 지점이라면 방문을 허용하도록 하는 방식으로 구현했다.


이렇게 구현할 것이라면 시작 지점도 다른 지점처럼 사전에 방문처리 해주더라도 상관이 없을 것이다.



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
 
#include<iostream>
#include<vector>
using namespace std;
 
typedef pair<int, int> pii;
const int dr[4] = { 1, 1, -1, -1 };
const int dc[4] = { 1, -1, -1, 1 };
int n, map[21][21];
bool vis[21][21], used[101];
 
pii src;
vector<int> arr;
int Max = -1;
void dfs(pii cur, int dir, int cnt) {
 
    if (cur.first == src.first && cur.second == src.second && cnt > 1) { //시작점으로 바로 되돌아가는 경우 방지
        if (Max < cnt) Max = cnt;
        return;
    }
 
 
    for (int i = 0; i < 2; i++) { //그대로 가거나 꺾거나
 
        if (dir + i >= 4) //이 이상 회전하는 것은 사각형이 아니다
            break;
 
        int nr = cur.first + dr[dir + i];
        int nc = cur.second + dc[dir + i];
    
        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
 
        if (!vis[nr][nc] && !used[map[nr][nc]]) {
 
            used[map[nr][nc]] = true;
            //arr.push_back(map[nr][nc]);
            dfs({ nr, nc }, dir + i, cnt + 1);
            //arr.pop_back();
            vis[nr][nc] = false;
            used[map[nr][nc]] = false;
 
        }
        else if (nr == src.first && nc == src.second)
            dfs({ nr, nc }, dir + i, cnt + 1);
    }
}
 
int main(void) {
    //    setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        //cout << '\n';
 
        for (int i = 0; i < n - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                src.first = i;
                src.second = j;
 
                used[map[i][j]] = true; // 출발 숫자 사용처리
                //vis[i][j] = true; 시작지점 방문처리 하지 않음 나중에 다시 돌아와야 하니까
 
                //arr.push_back(map[i][j]); //어떤 노드를 방문했는지 디버깅하기 위한 용도 
 
                dfs({ i, j }, 0, 0); //좌표, 방향, 거쳐간 노드수, 방향전환횟수
 
                used[map[i][j]] = false;
                arr.clear();
 
            }
        }
 
        cout << "#" << tc << ' ' << Max << '\n';
        Max = -1;
 
    }
    return 0;
}
 
 
cs



저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15
SWEA 4014: 활주로 건설 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo



가능한 구슬 투하 횟수만큼 중복 순열을 이용해서 구슬 투하 위치를 구한다.


구슬 투하 위치가 결정되면, BFS를 이용해서 폭탄들이 터지게 해준다.


이후에 중력에 의해서 공중에 있는 박스들이 내려오게 하는 처리는, 큐를 이용해서 바닥부터 빈 공간을 넣어주고, 이동해야할 블럭을 큐의 가장 상단에 있는 지점으로 결정해주면 된다.



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
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
int n, w, h, org[17][17], map[17][17], Min = 987654321;
bool vis[17][17];
struct Info {
    pii pos;
    int dis;
};
 
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
queue<Info> bomb;
 
vector<int> dropCol;
 
queue<pii> emp;
 
bool allZero() {
    
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (map[i][j] != 0) return false;
        }
    }
    return true;
}
void pick(int k) {
    if (k == n) {
 
        for (int i = 0; i < dropCol.size(); i++) {
            int c = dropCol[i];
            for (int r = 0; r < h; r++) {
                //구슬투하하고 터트리고 칸맞추고
                if (map[r][c] == 1 ) {
                    map[r][c] = 0;
                    break;
                }
                else if (map[r][c] > 1) {
                    bomb.push({ { r, c }, map[r][c] });
                    vis[r][c] = true;
 
                    while (!bomb.empty()) {
                        Info cur = bomb.front();
                        bomb.pop();
                        int dis = cur.dis;
                        map[cur.pos.first][cur.pos.second] = 0;
 
                        //4방향
                        for (int j = 1; j < dis; j++) {
                            for (int m = 0; m < 4; m++) {
                                int nr = cur.pos.first + dr[m] * j;
                                int nc = cur.pos.second + dc[m] * j;
                                
                                if (nr < 0 || nc < 0 || nr >= h || nc >= w) continue;
                                if (map[nr][nc] == 0 || vis[nr][nc]) continue;
                                if (map[nr][nc] >= 1) bomb.push({ { nr, nc }, map[nr][nc]});
                                else map[nr][nc] = 0;
                                vis[nr][nc] = true;
                            }
                        }
                        
                    }
 
                    for (int i = 0; i < h; i++)
                        for (int j = 0; j < w; j++)
                            vis[i][j] = false;
 
                    break;
                }
                
            }
            
            if (allZero()) {
                Min = 0;
                return;
            }
            
            //중력 처리
            for (int allCol = 0; allCol < w; allCol++) {
                for (int r = h - 1; r >= 0; r--) {
                    if (map[r][allCol] == 0) {
                        emp.push({ r, allCol });
                    }
                    else {
                        if (emp.empty()) continue;
                        pii dst = emp.front();
                        emp.pop();
                        map[dst.first][dst.second] = map[r][allCol];
                        map[r][allCol] = 0;
                        emp.push({ r, allCol });
                    }
                }
                while (!emp.empty()) emp.pop();
                
            }
            
        }
        
 
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] != 0) cnt++;
                map[i][j] = org[i][j];
            }
        }
        if (Min > cnt) Min = cnt;
    
        return;
    }
 
    if (Min == 0) return;
    for (int i = 0; i < w; i++) {
        dropCol.push_back(i);
        pick(k + 1);
        dropCol.pop_back();
    }
}
 
int main(void) {
    setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
 
        cin >> n >> w >> h;
        for (int i = 0; i < h; i++) 
            for (int j = 0; j < w; j++) {
                cin >> org[i][j];
                map[i][j] = org[i][j];
            }
        
        //cout << '\n';
        //0~w-1까지 수중에 n개 중복 허용하고 고르기 (순서 상관 X)
        pick(0);
        
        cout << "#" << tc << ' ' << Min << '\n';
        Min = 987654321;
 
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 4014: 활주로 건설 (C++)  (0) 2019.10.15
SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE




테스트 케이스 2번의 경우를 잘 처리해야 한다.


그냥 채집할 수 있는 가장 큰 꿀을 그리디하게 채집하게 되면, 7과 5,5 를 비교한다고 했을 때, 


이윤이 5 두개를 채집했을 경우 더 크기 때문에, 결국 모든 경우에 대해서 이윤을 비교하기 위해 완전탐색이 필요함을 알 수 있다.



일단 사람이 1명이라고 생각하고, 조건에 따라 채집할 수 있는 벌꿀의 위치별 최대 이윤을 시작 지점과 함께 벡터에 저장했다.


이후에 그 벡터에서 두 개를 골라서 (두명이 채집하니까) 그 위치가 겹치지 않으면서 이윤의 합이 최대인 경우를 답으로 출력해주면 된다.



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
 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
 
int map[11][11], n, m, c;
 
bool cmp(int a, int b) {
    return a > b;
}
 
struct Info {
    pii pos;
    int pft;
};
 
bool cmpCandi(Info a, Info b) {
    return a.pft > b.pft;
}
 
 
bool vis[11];
vector<int> arr;
 
int tmpMax = -1;
void dfs(int k, int Sum, int bef, vector<int>& tmp) {
    if (Sum >= c || k == m) {
        //최대이윤인지 확인
        
        bool reduce = false;
        if (Sum > c) { //수집 가능한 양을 초과했으면 직전 수집 양을 감소 시켜줘야함
            Sum -= bef;
            reduce = true; //종료 조건에서 arr벡터 pop을 해주면 다른 부분에서 중복 pop이 되기 때문에 이렇게 처리함
        }
 
        int Size = arr.size();
        if (reduce) Size--; //하나 덜 검사하도록 처리
 
        int tmpPft = 0;
        for (int i = 0; i < Size; i++)
            tmpPft = tmpPft + arr[i] * arr[i];
 
        if (tmpMax < tmpPft) tmpMax = tmpPft; //최대 이윤 갱신
        return;
    }
 
 
    for (int i = 0; i < tmp.size(); i++) {
        if (vis[i]) continue;
        vis[i] = true;
        
        arr.push_back(tmp[i]);
        
        dfs(k+1, Sum+tmp[i], tmp[i], tmp);
        vis[i] = false;
        arr.pop_back();
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n >> m >> c;
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        vector<Info> candi; //시작지점, 가능 꿀
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n-m; j++) {
                //시작점 i행j열
                vector<int> tmp;
                for (int k = j; k < j + m; k++) 
                    tmp.push_back(map[i][k]); //꿀 후보 추가
                
                //최대 이윤내는 꿀 골라서 이윤 계산
 
                tmpMax = -1;
        
                dfs(0, 0, 0, tmp); //인덱스, 합, 이전까지합,
 
                Info tmpInfo;
                tmpInfo.pos = { i, j };
                tmpInfo.pft = tmpMax;
                candi.push_back(tmpInfo); //시작지점, 이익 push
                
                tmp.clear();
            }
        }
 
        sort(candi.begin(), candi.end(), cmpCandi);
 
        int Max = -1;
        for (int i = 0; i < candi.size(); i++) {
            for (int j = i + 1; j < candi.size(); j++) {
                if (candi[i].pos.first == candi[j].pos.first) { //같은 칸에서 두명이 채집한 경우 pass
                    if (candi[j].pos.second <= candi[i].pos.second + m - 1 ||
                        candi[i].pos.second <= candi[j].pos.second + m - 1) continue;
                }
                if (candi[i].pft + candi[j].pft > Max) Max = candi[i].pft + candi[j].pft;
 
            }
        }
 
        printf("#%d %d\n", tc, Max);
        candi.clear();
    }
    
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE




통로를 통해서 이동을 하는데, 현재의 통로에서 목적지의 통로로 이동할 수 있는지 확인해가며 BFS를 구현해주면 된다.




BFS의 특성상 가까운 지점을 무조건 먼저 방문하게 되므로, 임계 거리를 방문하는 순간 BFS를 종료해주면 된다.




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
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
 
int m[51][51], dis[51][51];
vector<vector<int> > dr = { {0,0,1,-1}, {1,-1}, {0,0}, {0, -1},{1, 0},{1,0}, {-1,0} }; //동서남북
vector<vector<int> > dc = { {1,-1,0,0}, {0,0}, {1,-1}, {1,0}, {0,1}, {0, -1}, {0,-1} };
 
queue<pii> q;
 
int r, c, mr, mc, Time; //m~ 맨홀 위치
int cnt = 0;
 
int findDir(int nr, int nc) {
    if (nr == 0 && nc == 1) return 1;
    else if (nr == 0 && nc == -1) return 2;
    else if (nr == 1 && nc == 0) return 3;
    else return 4;
}
 
bool dirCheck(int srcDir, int desIdx) {
    if (srcDir == 1) { //동쪽으로 이동중인 경우
        if (desIdx == 2 || desIdx == 4 || desIdx == 5) return false;
        else return true;
    }
    else if (srcDir == 2) { //서쪽으로 이동중인 경우
        if (desIdx == 2 || desIdx == 6 || desIdx == 7) return false;
        else return true;
    }
    else if (srcDir == 3) { //남쪽으로 이동중인 경우
        if (desIdx == 3 || desIdx == 5 || desIdx == 6) return false;
        else return true;
    }
    else { //북쪽으로 이동중인 경우
        if (desIdx == 3 || desIdx == 4 || desIdx == 7) return false;
        else return true;
    }
}
 
void bfs(pii st) {
    q.push(st);
    dis[st.first][st.second]++; //시작점 시간 1로
    cnt++;
    
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        if (dis[cur.first][cur.second] >= Time) return; //탈출조건
 
        int deltaIdx = m[cur.first][cur.second]; //1나오면 0으로 써야함(좌표 이동 벡터 인덱스)
        
        for (int i = 0; i < dr[deltaIdx - 1].size(); i++) {
            int nr = cur.first + dr[deltaIdx - 1][i];
            int nc = cur.second + dc[deltaIdx - 1][i];
 
            if (nr < 0 || nc < 0 || nr >= r || nc >= c || dis[nr][nc] >= 1) continue;
            if (m[nr][nc] == 0) continue;
 
            int curDir = findDir(dr[deltaIdx - 1][i], dc[deltaIdx - 1][i]); //어느 방향으로 이동중인지
            
            
            if (!dirCheck(curDir, m[nr][nc])) continue; //이동할 수 없는 방향
 
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
 
            cnt++;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
 
        cin >> r >> c >> mr >> mc >> Time;
        
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                cin >> m[i][j]; 
        
        bfs({ mr, mc });
        
        printf("#%d %d\n", tc, cnt);
 
        //초기화
        cnt = 0;
        while (!q.empty()) q.pop();
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                dis[i][j] = 0;
    }
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08
SWEA 1952: 수영장 (C++)  (0) 2019.10.04

+ Recent posts

티스토리툴바