반응형

www.acmicpc.net/problem/13460

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

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
#include <iostream>
#include <queue>
#define pii pair<int, int>
#define ppii pair<pii, pii>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, m, cnt;
char arr[11][11];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int visited[10][10][10][10];
queue<ppii> q;
pii r, b, hole;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    rep(i, n) {
        rep(j, m) {
            cin >> arr[i][j];
            if (arr[i][j] == 'R')
                r = { i,j };
            else if (arr[i][j] == 'B')
                b = { i,j };
            else if (arr[i][j] == 'O')
                hole = { i,j };
        }
    }
 
    q.push({ r, b });
    visited[r.first][r.second][b.first][b.second] = 1;
    while (!q.empty()) {
        if (cnt > 10) {
            cout << -1;
            exit(0);
        }
        int size = q.size(); 
        while (size--) {
            pii now_r = q.front().first;
            pii now_b = q.front().second;
            q.pop();
            
            // 빨간 공 O 도착했으면????
            if (arr[now_r.first][now_r.second] == 'O' && arr[now_b.first][now_b.second] != 'O') {
                cout << cnt;
                exit(0);
            }
 
            rep(i, 4) {
                int nrx = now_r.first;
                int nry = now_r.second;
                int nbx = now_b.first;
                int nby = now_b.second;
 
                // 다음 칸이 벽 아니면 이동
                while (arr[nrx + dx[i]][nry + dy[i]] != '#') {
                    if (arr[nrx][nry] == 'O') break;
                    nrx += dx[i];
                    nry += dy[i];
                }
 
                // 다음 칸이 벽 아니면 이동
                while (arr[nbx + dx[i]][nby + dy[i]] != '#') {
                    if (arr[nbx][nby] == 'O') break;
                    nbx += dx[i];
                    nby += dy[i];
                }
 
 
                // 빨간공, 파란공 겹치면????????    -> 이 부분 때문에 못 풂
                if (nrx == nbx && nry == nby) {
                    if (arr[nrx][nry] != 'O') {
                        // 더 많이 이동한 공을 한 칸 뒤로 이동
                        int r_dist = abs(nrx - now_r.first) + abs(nry - now_r.second);
                        int b_dist = abs(nbx - now_b.first) + abs(nby - now_b.second);
                        if (r_dist > b_dist) {
                            nrx -= dx[i];
                            nry -= dy[i];
                        }
                        else {
                            nbx -= dx[i];
                            nby -= dy[i];
                        }
                    }
                }
                
                // 이미 방문했으면 continue
                if (visited[nrx][nry][nbx][nby]) continue;
 
                // 방문 처리 + 큐에 삽입
                visited[nrx][nry][nbx][nby] = 1;
                q.push({ {nrx, nry}, {nbx, nby} });
            }
        }
        cnt++;
    }
    cout << -1;
}
cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 13458  (0) 2021.04.29
백준 3190  (0) 2021.04.29
백준 12100 [복습 필수]  (0) 2021.03.03
백준 20055  (0) 2021.02.23
백준 15685 [복습 필수]  (0) 2021.02.23
반응형

www.acmicpc.net/problem/1062

 

1062번: 가르침

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문

www.acmicpc.net

1
2
3
4
5
6
7
8
// 백트래킹으로 사용하지 않은 문자 찾기
for (int i = now; i < 26; i++) {
    if (!visited[i]) {
        visited[i] = 1;
        dfs(i + 1, cnt + 1);
        visited[i] = 0;
    }
}
 cs

 

 

 

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
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int visited[26];
vector<vector<char> > v;
int n, k, cnt = 5, ans;
string str;
void dfs(int now, int cnt) {
    if (cnt == k) {
        int temp = 0;
        for (vector<char> vec : v) {
            int j;
            // 방문 안 한 글자 있으면 break
            for (j = 0; j < vec.size(); j++) 
                if (!visited[vec[j] - 'a']) break;
            
            // 끝까지 돌았으면 temp++
            if (j == vec.size())
                temp++;
        }
        ans = max(ans, temp);
        return;
    }
 
    // 백트래킹으로 사용하지 않은 문자 찾기
    for (int i = now; i < 26; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            dfs(i + 1, cnt + 1);
            visited[i] = 0;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    v.resize(n);
    // 앞 뒤 4글자 방문
    visited['a' - 'a'] = 1;
    visited['n' - 'a'] = 1;
    visited['t' - 'a'] = 1;
    visited['i' - 'a'] = 1;
    visited['c' - 'a'] = 1;
 
    // 가운데 글자 입력
    rep(i,n){
        cin >> str;
        for (int j = 4; j < str.size() - 4; j++)
            v[i].push_back(str[j]);
    }
    if (k < 5) {
        cout << 0;
        return 0;
    }
    dfs(0, cnt);
    cout << ans;
}
 cs
반응형

'백준 > 백트래킹' 카테고리의 다른 글

백준 2580  (0) 2021.02.24
N-Queen 복습 (백준 9663)  (0) 2021.02.23
백준 16198  (0) 2021.02.23
백준 15658  (0) 2021.02.23
백준 1248 [복습 필수]  (0) 2021.02.15
반응형

www.acmicpc.net/problem/1208

 

1208번: 부분수열의 합 2

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

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
#include <iostream>
#define rep(i,n) for(ll i=0;i<n;i++)
#define ll long long
using namespace std;
ll arr[41], a1[4000001], a2[4000001];
ll n, s, ans;
 
void calc() {
    ll mask = 0;
    ll tmp = 0;
    ll len = n / 2;
    // 배열 왼쪽
    while (mask < (1 << len)) {
        tmp = 0;
        rep(i, len) 
            tmp += ((mask >> i) & 1)* arr[i];
        
        a1[tmp + 2000000]++;
        mask++;
    }
 
    // 배열 오른쪽
    mask = 0;
    if (n % 2 == 1)
        len++;
    
    while (mask < (1 << len)) {
        tmp = 0;
        rep(i, len)
            tmp += ((mask >> i) & 1)* arr[i + n / 2];
        
        a2[tmp + 2000000]++;
        mask++;
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    rep(i, n)
        cin >> arr[i];
 
    // 1. 배열 나눠서 부분수열 계산
    calc();
    
    // 2. 투 포인터로 탐색
    ll p1 = 0, p2 = 4000000;
    if (s == 0)
        ans--;
    s += 4000000;
    while (1) {
        while (p1 + p2 > s)        // s보다 크면 p2를 이동시켜서 더 작게 만들기
            p2--;
        while (p1 + p2 < s)        // s보다 작으면 p1을 이동시켜서 더 크게 만들기
            p1++;
        if (p1 > 4000000 || p2 < 0) break;    // 범위 벗어나면 종료
        if (p1 + p2 == s)        // s와 같으면 더하기
            ans += a1[p1] * a2[p2];
        p1++;                    // 다음 탐색 진행을 위해 p1 오른쪽으로 이동
    }
    cout << ans;
}
 cs
반응형

'백준 > 브루트포스' 카테고리의 다른 글

백준 14225  (0) 2021.02.23
백준 14391  (0) 2021.02.15
백준 1182  (0) 2021.02.15
백준 6064  (0) 2021.02.13
백준 1107 [복습 필수]  (0) 2021.02.13

+ Recent posts

티스토리툴바