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



백트래킹을 활용하면 풀리는 문제이다.


현재 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
#pragma warning(disable :4996)
#include<iostream>
#include<string>
using namespace std;
const int dr[4= { 0,0,1,-1 };
const int dc[4= { 1,-1,0,0 };
typedef pair<intint> pii;
int row, col, Max = 0;
char m[21][21], arr[100];
bool vis[21][21], used[26];
void Print() {
    cout << '\n';
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            cout << m[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}
 
void dfs(pii here, int k) { //지금까지 k개 지나옴
    
    if (Max < k) Max = k; 
    for (int i = 0; i < 4; i++) {
        int nr = here.first + dr[i];
        int nc = here.second + dc[i];
        if (nr < 1 || nc < 1 || nr > row || nc > col) continue;
        
        if (!used[m[nr][nc] - 'A'&& !vis[nr][nc]) { //그 문자를 안 썼고 그 지점을 거쳐 오지 않았으면
            used[m[nr][nc] - 'A'= true//해당 문자 사용중 
            vis[nr][nc] = true//방문
            arr[k] = m[nr][nc];
            dfs({ nr, nc }, k + 1);
            vis[nr][nc] = false;
            used[m[nr][nc] - 'A'= false;
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> row >> col;
    for (int i = 1; i <= row; i++) {
        string input;
        cin >> input;
        for (int j = 0; j < col; j++
            m[i][j+1= input[j];
    }
 
    used[m[1][1- 'A'= true//시작점은 항상 사용중
    vis[1][1= true//항상 방문중
    dfs({ 11 }, 1);
    cout << Max;
    return 0;
}
 
cs


배열에서, 특정 원소의 개수를 파악하는 것을 upper_bound 그리고 lower_bound를 활용해서 할 수 있다.


1
2
3
4
5
6
7
8
9
10
sort(x.begin(), x.end());
 
    vector<ll>::iterator low, high;
    for (int i = 0; i < x.size(); i++) {
        if (mp.find(x[i]) == mp.end()) {
            low = lower_bound(x.begin(), x.end(), x[i]);
            high = upper_bound(x.begin(), x.end(), x[i]);
            mp.insert({ x[i], high - low });
        }
    }
cs



당연하게도 두 bound의 특징을 활용해서 특정 원소의 개수를 파악하기 위해서는 정렬이 필수적이다.


 코드의 경우, low에는 처음으로 벡터의 원소가 x[i] 이상이 되는 원소의 iterator가 반환되고,


high에는 벡터의 원소중, 처음으로 x[i] 초과가 되는 원소의 iterator가 저장된다.



이때 high 혹은 low에서 x.begin()을 빼주면 몇번째 위치인지를 파악할 수 있는 것이고,


이 과정을 생략하고 high와 low의 차이를 구하면, 두 iterator의 위치 차이를 구할 수 있기 때문에, x[i]의 개수가 구해지는 것이다.



'Programming Language > C++' 카테고리의 다른 글

STL list insert, erase (C++)  (1) 2019.09.02
string 대소문자 변환  (0) 2019.08.25
priority_queue  (0) 2019.08.14
(C++) abs 함수의 사용  (0) 2019.08.07
(C++) list STL 출력 및 iterator  (0) 2019.08.04

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



특정 위치까지 이동할 때 최소 비용을 구해주고, 최소 비용으로 그 위치까지 도달하는 방법의 수를 구해주면 된다.


처음에는 목적지만 중복해서 방문할 수 있도록 해주면 된다고 생각했는데, 이렇게 접근하게 되면


1 -> 2로 가는경우 1+1 로 2로 가는 경우와, 1 * 2로 2로 가는 경우를 모두 잡아낼 수 있지만,


1 -> 4로 가는 경우를 생각해보면 1+1 -> 2, 2 *2 - > 4 로 가는 경우에서 2를 방문 처리한 이후에 재방문을 허용하지 않기 때문에 문제가 된다.


따라서 재방문을 목적지가 아니더라도 허용해주어야 하는데, 당연히 모든 경우에 허용해주면 안되고, 이전에 방문했을 때의 비용과 같은 경우에만 허용해주면 된다.


당연하게도 이전에 방문했던 비용보다 작은 비용으로 재방문하는 경우는 나오지 않는다.



즉, 목적지가 아닌 지점을 재방문 할 때에는, 이미 설정되어 있는 그 지점으로 이동하는 비용과, 현재 지점 + 1 을 비교해서, 같은 경우에는 재방문을 허용한다(큐에 삽입).



목적지인 지점을 재방문 할 경우에는, 위와 같이 비용 비교를 해주고, 동일 비용으로 재방문하는 경우 카운트를 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
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
int m[100001], src, dst, dis[100001];
const int d[3= { 0,1,2 };
queue<int> q;
int cnt = 1//무조건 한 가지 방법은 나온다
void bfs() {
    q.push(src);
    dis[src]++;
    while (!q.empty()) {
        int qs = q.size();
        for (int t = 0; t < qs; t++) {
            int cur = q.front();
            q.pop();
            
            int np;
            for (int i = 0; i < 3; i++) {
                if (d[i] == 0)
                    np = cur + 1;
                else if (d[i] == 1)
                    np = cur - 1;
                else
                    np = cur * 2;
                if (np < 0 || np > 100000continue
                
                //이전에 방문한 적이 있더라도, 동일 비용으로 방문이 가능한 경우
                if (dis[cur] + 1 == dis[np] && dis[np] >= 0){ 
                    if (np == dst) { //목적지인 경우, 그 이후를 탐색할 필요가 없으므로 push 하지 않음
                        cnt++;
                        continue;
                    }
                    else { //이전에 방문한 곳을 여러 방법으로 거쳐갈 수 있으므로 push
                        q.push(np);
                        continue;
                    }
                    
                    //_sleep(500);
                }
 
                //위의 경우를 제외하고 비용이 양수인 경우는, 최소 비용으로 방문하는 경우가 아님
                if (dis[np] >= 0continue
 
                //방문하지 않은 곳을 방문해줌
                dis[np] = dis[cur] + 1;
                q.push(np);
            }
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> src >> dst;
    for (int i = 0; i <= 100000; i++)
        dis[i] = -1;
    bfs();
    
    cout << dis[dst] << '\n' << cnt;
    
    return 0;
}
 
cs


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



통 A가 비었을때, C에 존재할 수 있는 모든 물의 양의 경우를 출력해주면 된다.


물이 이동할 수 있는 방법은 6가지이다.


a->b, b->c ... 


초기에 각 통의 물의양은 0,0,C 이고, 6가지 모든 경우를 큐에 삽입해주고, a가 0인 순간에만 c의 물의 양을 기록해서 마지막에 출력해주면 된다.


보통 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
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
struct Info {
    int a, b, c; //a b c 물통의 현재 물의 양
};
queue<Info> q;
bool cVis[201], abVis[201][201]; 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A, B, C;
    cin >> A >> B >> C; //통의 부피
 
    q.push({ 00, C }); //초기 물은 C에만 가득있음
    //abVis[0][0] = true;
    //cVis[C] = true;
 
    while (!q.empty()) {
        Info cur = q.front(); //현재상태
        q.pop();
        
        //printf("%d %d %d\n", cur.a, cur.b, cur.c);
        
        if (abVis[cur.a][cur.b]) continue;
 
        abVis[cur.a][cur.b] = true;
 
        if (cur.a == 0) {
            cVis[cur.c] = true;
            //printf("%d 추가\n", cur.c);
        }
 
        // a->b
        if (cur.a + cur.b > B) {
            q.push({ cur.a - (B - cur.b), B, cur.c });
            //abVis[cur.a - (B - cur.b)][B] = true;
        }
        else {
            q.push({ 0, cur.a+cur.b, cur.c });
            //abVis[0][cur.a + cur.b] = true;
        }
        // b -> a
        if (cur.b + cur.a > A) {
            q.push({ A, cur.b-(A-cur.a), cur.c });
            //abVis[A][cur.b - (A - cur.a)] = true;
        }
        else {
            q.push({ cur.a + cur.b, 0, cur.c });
            //abVis[cur.a + cur.b][0] = true;
        }
 
        // b->c
        if (cur.b + cur.c > C) {
            q.push({ cur.a, cur.b - (C - cur.c), C });
            //abVis[cur.a][cur.b - (C - cur.c)] = true;
        }
        else {
            q.push({ cur.a, 0, cur.b + cur.c });
        //    abVis[cur.a][0] = true;
        }
 
        //c->b
        if (cur.b + cur.c > B) {
            q.push({cur.a, B, cur.c-(B-cur.b) });
            //abVis[cur.a][B] = true;
        }
        else {
            q.push({ cur.a, cur.b + cur.c, 0 });
            //abVis[cur.a][cur.b + cur.c] = true;
        }
 
        //c->a
        if (cur.c + cur.a > A) {
            q.push({A, cur.b, cur.c-(A-cur.a) });
            //abVis[A][cur.b] = true;
        }
        else {
            q.push({ cur.a + cur.c, cur.b, 0 });
        //    abVis[A][cur.b] = true;
        }
 
        //a->c
        if (cur.c + cur.a > C) {
            q.push({ cur.a-(C-cur.c), cur.b, C });
            //abVis[cur.a - (C - cur.c)][cur.b] = true;
        }
        else {
            q.push({ 0, cur.b, cur.a + cur.c });
            //abVis[0][cur.b] = true;
        }
 
    }
 
    for (int i = 0; i <= C; i++)
        if (cVis[i]) cout << i << ' ';
 
    return 0;
}
 
cs


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



2차원 배열을 문자열로 맵핑해서 해결한다.



1 2 3

4 5 6

7 8 0 


위와 같은 2차원 배열이라면 "123456780" 이러한 문자열이 되는 것이다.


0의 인덱스로부터 2차원 배열에서 0의 위치를 알아낼 수 있다.



한번의 시행에서, 빈칸의 위치를 옮길 수 있는 위치를 찾아준 다음에, 이전 시행에서 찾은 경우만큼만 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
#include<iostream>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
 
const int dzero[4= { -33-11 }; //상하좌우
const int dr[4= { -1,1,0,0 };
const int dc[4= { 0,0,-11 };
 
int main(void) {
    string str ="", dst = "123456780";
    
    for (int i = 0; i < 9; i++) {
        int input;
        cin >> input;
        str += input + '0';
    }
    
    set<string> vis;
    vis.insert(str);
    
    queue<string> q;
    q.push(str);
    int cnt = 0;
    
    while(!q.empty()) {
        int qSize = q.size(); //이전 시행에 찾았던 0이 이동 가능한 경우만 실행
        for (int i = 0; i <qSize; i++) {
            string cur = q.front(); //현재 문자열
            q.pop();
 
            if (cur == dst) { //목적 문자랑 같으면 종료
                cout << cnt;
                return 0;
            }
            //cnt++;
 
            int zeroPos=0//0위치 검색
            for (int j = 0; j < cur.length(); j++) {
                if (cur[j] == '0') {
                    zeroPos = j;
                    break;
                }    
            }
            
            //문자열의 0의 위치로부터 2차원 배열에서의 위치를 맵핑
            int zeroR = zeroPos / 3;
            int zeroC = zeroPos % 3;
 
            for (int j = 0; j < 4; j++) { //0이 움직일 수 있는 방향을 찾음
                int nr = zeroR + dr[j];
                int nc = zeroC + dc[j];
                if (nr < 0 || nc < 0 || nr >= 3 || nc >= 3continue;
                
                string next = cur;
                swap(next[zeroPos], next[zeroPos + dzero[j]]);
 
                if (vis.find(next) == vis.end()){
                    vis.insert(next);
                    q.push(next);
                }
            }
        }
        cnt++//이전에 찾은 경우들 다 해보고 
    }
    cout << -1;
    return 0;
}
 
cs



참고: http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220438835865

+ Recent posts