BOJ : https://www.acmicpc.net/problem/2186

github : https://github.com/junho0956/Algorithm/blob/master/2186/2186/%EC%86%8C%EC%8A%A4.cpp

 

처음에는 BFS, DFS 로 둘다 탐색해보았는데

전부다 시간초과가 되서 멘탈이 나갔던 문제였다. 마침 설날이라 놀고싶기도 했고,, ??

 

처음에 bfs 에 의해 시간초과가 발생해서

시도해본게 dfs 로 첫 발생지점에 대한 dp 였다.

2중포문을 돌면서 첫 알파벳을 찾는 순간 dp를 초기화하고

이 부분에 대한 dfs 를 돌면서 탐색하지 않아도 되는 부분은 줄여나가는 식으로 했었다.

역시 시간초과였다.

 

그래서 다른방법을 생각해보았다.

통째로 dp를 적용할 수 있을까?

그래서 생각한게 3차원 배열의 dp였다

원래 dfs 를 적용했을때는 100*100 dp 를 사용했는데

3차원 배열을 사용하면 인덱스별로 dp 를 적용할 수 있을 것 같았다.

그래서 사용한 배열이 100*100*80 dp 이고

 

** 현재 탐색하고있는 알파벳 부분의 인덱스를 알고 있을 때 dp 값이 존재하지 않는다면 탐색,

** 존재한다면 리턴 하는 식으로 구현해보았다.

 

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
// bfs 로 풀어보니 시간초과가 발생한다
// dfs 로 풀게되면 시간초과가 발생하긴 하는데, dp 같은 느낌의 방법을
// 적용해볼 수 있을 것 같다.
 
#include <iostream>
#include <string>
using namespace std;
 
// 최대길이가 80 이라고했으니 80에 대한 dp 배열을 잡는다.
// 80 의 의미는 임의의 (y,x) 에 도착했을 때
// 현재 문자열의 인덱스 중 몆번째 인덱스를 탐색하는지 알고있다면,
// 이때 dp 배열이 초기화상태가 아니라면 이미 이 부분은 탐색된 것이니
// 탐색을 중단하고 값을 가져간다는 느낌으로 간다.
int dp[100][100][80];
char arr[100][100];
int mx[4] = { -1,1,0,0 };
int my[4] = { 0,0,1,-1 };
int N, M, K;
string ans;
 
int solve(string str, int y, int x, int idx) {
 
    if (dp[y][x][idx] != -1) return dp[y][x][idx];
 
    if (str.size() >= ans.size()) return 1;
    dp[y][x][idx] = 0;
    for (int i = 0; i < 4; i++) {
        int yy = y, xx = x;
        for (int j = 1; j <= K; j++) {
            yy += my[i];
            xx += mx[i];
            if (yy >= 0 && xx >= 0 && yy < N && xx < M && arr[yy][xx] == ans[idx+1]) {
                dp[y][x][idx] += solve(str + ans[idx+1], yy, xx, idx + 1);
            }
        }
    }
 
    return dp[y][x][idx];
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> arr[i][j];
 
    cin >> ans;
 
    int total = 0;
    string f;
    f.push_back(ans[0]);
 
    // 밑부분에서 solve(f,i,j,0) 을 할때 dp return 을 하지 않기 때문에
    // 일부러 -1 로 초기화 해주었다.
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) for (int k = 0; k < 80; k++) dp[i][j][k] = -1;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == ans[0]) {
                total += solve(f, i, j, 0);
            }
        }
    }
 
    cout << total;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 5014번 스타트링크  (0) 2020.01.31
BOJ 3108번 로고  (0) 2020.01.31
BOJ 2251번 물통  (0) 2020.01.24
BOJ 1525번 퍼즐  (0) 2020.01.24
BOJ 9019번 DSLR  (0) 2020.01.23

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

github : https://github.com/junho0956/Algorithm/blob/master/2251/2251/%EC%86%8C%EC%8A%A4.cpp

 

문제에서 요구하는대로 구현하기는 했는데 썩 깔끔하지는 않다.

그 이유는 .. 아직 set 사용법에 대한 정확한 사용법을 몰라서

 

처음에는 typedef 로 선언해둔 구조체형인 pii 를 이용해서

set<pii> 형식으로 사용하였는데

다 코드한 후에 실행해보니, typedef 템플릿에 대한 어떤 컴파일 오류가 발생하였다.

오류를 이해하기 힘들어 이번에는 아래의 piiset 과 같은 선언을 이용해보았는데

다행히 컴파일오류가 나지 않아 AC 를 받게 되었다.

 

핵심은 문제가 요구하는 그대로 따라가주면 된다.

한 컵을 다 채우거나 자신의 컵이 비워질떄까지 채우기 위한 조건 그대로 코드해주면 된다.

 

맨 아래의 erase ( unique ~ ) 는 중복을 제거하는 방법으로,

 

간단히 설명하면

erase 가 컨테이너의 값을 지우는 함수이고

unique 는 컨테이너 내부의 값들 중 중복의 값이 없게 나열하는 함수이다.

unique 가 종료되고 나면 중복 정리가 끝난 뒷부분에 이터레이터가 반환되고,

이 부분부터 end 까지 erase 가 실행되어 중복제거가 완료된다.

 

set 을 쓰고나니 코드하는 부분이 더욱 편해진 것은 사실인 것 같다.

좀더 자주 사용해보도록 해야겠다.

 

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 <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
typedef struct pii {
    int a, b, c;
};
typedef pair<int, pair<int, int> > piiset;
 
vector<int> v;
queue<pii> q;
set<piiset> visit;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int A, B, C;
    cin >> A >> B >> C;
 
    q.push({ 0, 0, C });
 
    while (!q.empty()) {
        pii value = q.front();
        piiset valueset;
        valueset.first = value.a;
        valueset.second.first = value.b;
        valueset.second.second = value.c;
        q.pop();
 
        if (visit.find(valueset) != visit.end()) continue;
        visit.insert(valueset);
 
        if (value.a == 0) v.push_back(value.c);
        else {
            if (value.a <= B - value.b) q.push({ 0,value.b + value.a,value.c });
            else q.push({ value.a - (B - value.b), B, value.c });
            if (value.a <= C - value.c) q.push({ 0,value.b,value.c + value.a });
            else q.push({ value.a - (C - value.c), value.b, C });
        }
 
        if (value.b <= A - value.a) q.push({ value.a + value.b, 0, value.c });
        else q.push({ A, value.b - (A - value.a), value.c });
        if (value.b <= C - value.c) q.push({ value.a, 0, value.c + value.b });
        else q.push({ value.a, value.b - (C - value.c), C });
 
        if (value.c <= A - value.a) q.push({ value.a + value.c, value.b, 0 });
        else q.push({ A, value.b, value.c - (A-value.a) });
        if (value.c <= B - value.b) q.push({ value.a, value.b + value.c, 0 });
        else q.push({ value.a, B, value.c - (B - value.b) });
    }
 
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 3108번 로고  (0) 2020.01.31
BOJ 2186번 문자판  (0) 2020.01.27
BOJ 1525번 퍼즐  (0) 2020.01.24
BOJ 9019번 DSLR  (0) 2020.01.23
BOJ 1963번 소수 경로  (0) 2020.01.23

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

github : https://github.com/junho0956/Algorithm/blob/master/1525/1525/%EC%86%8C%EC%8A%A4.cpp

 

퍼즐은 내 초보적 지식으로는 해결하는데 어려움이 있는 문제였다.

 

숫자가 9개가 주어진다는 점에서 3*3 배열을 사용하는 것이 아닌

9개를 나열한 int형 수를 사용하면 된다는 점까지는 접근하였다.

 

하지만 이 정보가지고는 BFS 를 돌리는데 문제가 있었다.

9자리 int형이면 정말 가능한 모든 범위는 987654321 까지는 봐야한다는 점인데,

이걸 방문배열을 통해서 확인하려고 하니

저정도의 큰 크기를 가진 배열을 사용할수도 없고,

그렇다고 만들어진 수를 이용해서 이분탐색으로 찾아볼려니

매번 정렬해야한다는 단점이 있어서 시간초과를 어떤식으로 해결해야할지 접근을 못했었다.

 

그러다가 알게된 방법이 set , map 이라는 STL 템플릿이였고,

이중에서 set 을 사용하였다.

set 을 아직 공부를 하지않아 정확한 개념을 모르지만, 어떤 값에 대한 유무를 판별하는데 사용된다고 한다.

내부 구현을 몰라서 뭐 어떤식으로 값에 대한 유무 판단을 하는 것인지는 모르겠지만

일단 사용해보았는데? 정말 빨랐다.

디버깅을 해보았는데 살짝 Heap 같이 원소를 넣을때마다 자동정렬이 되는 것을 확인하였다.

 

조만간 set의 내부구현, 작동원리에 대해서 공부하여 포스팅하는 시간을 가져보도록 해야겠다.

 

이 문제의 핵심은,

3*3 배열을 사용하는 것이 아닌, 9자리 int 형 숫자를 이용하여

완전탐색 식의 BFS 을 통해 문제를 해결하는 것이고

 

주의할 점은, 0이 아닌 9를 사용해야한다는점 ( 위에서도 설명했다 )

맨 왼쪽, 맨 오른쪽은 -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
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
 
string ans = "123456789";
queue<pair<string, int> > q;
set<int> visit;
 
bool check_visit(string str) {
    int key = stoi(str);
    
    if (visit.find(key) != visit.end()) return false;
    else return true;
}
 
void changing(string change, int index, int cnt, int location) {
    if (location +index >= 0 && location + index < 9) {
 
        if (location % 3 == 1 || (location % 3 == 2 && index != 1) || (location % 3 == 0 && index != -1)) {
            swap(change[location], change[location + index]);
            if (check_visit(change)) q.push({ change,cnt + 1 }), visit.insert(stoi(change));
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int n;
    string str;
    bool solve = false;
 
    for (int i = 0; i < 9; i++) {
        cin >> n;
        if (n == 0) n = 9;
        str.push_back(n+'0');
    }
    
    q.push({ str,0 });
    while (!q.empty()) {
        string check = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (check.compare(ans) == 0) {
            cout << cnt;
            solve = true;
            break;
        }
        int location = check.find('9');
        
        changing(check, -3, cnt, location);
        changing(check, 3, cnt, location);
        changing(check, -1, cnt, location);
        changing(check, 1, cnt, location);
    }
 
    if (!solve) cout << "-1";
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2186번 문자판  (0) 2020.01.27
BOJ 2251번 물통  (0) 2020.01.24
BOJ 9019번 DSLR  (0) 2020.01.23
BOJ 1963번 소수 경로  (0) 2020.01.23
BOJ 13913번 숨바꼭질4  (0) 2020.01.23

BOJ : https://www.acmicpc.net/problem/9019

github : https://github.com/junho0956/Algorithm/blob/master/9019/9019/%EC%86%8C%EC%8A%A4.cpp

 

문제에서 요구하는 그대로 작성하였다.

코드를 정확히 하지않으면 1000 같은 숫자는 L 했을 때 1 이 되고 R 했을 때 100 이 되는 경우들에 대한

반례가 분명 생길 것 같아서

어차피 4자리 숫자이니 한자리씩 가지고 와서 체크후, 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
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
 
// 한자리씩 가지고오기 위한 구조체
typedef struct number {
    int init[4];
};
number result;
 
// 어떤 명령어를 사용했는지 체크하기 위한 배열
pair<char, int> parent[10000];
bool visit[10000];
int Testcase, A, B, now;
queue<int> q;
stack<char> s;
 
void now_check(int num) {
 
    for (int i = 0; i < 4; i++) result.init[i] = 0;
 
    int idx = 3;
    while (num) {
        result.init[idx--] = num % 10;
        num /= 10;
    }
}
 
void D() {
    int temp = result.init[0];
    for (int i = 1; i < 4; i++) {
        temp = temp * 10 + result.init[i];
    }
 
    temp = (temp * 2) % 10000;
    if (!visit[temp] && parent[temp].first == NULL) {
        parent[temp].first = 'D';
        parent[temp].second = now;
        q.push(temp);
    }
}
 
void S() {
    int temp = result.init[0];
    for (int i = 1; i < 4; i++) {
        temp = temp * 10 + result.init[i];
    }
 
    if (temp == 0) temp = 9999;
    else temp--;
 
    if (!visit[temp] && parent[temp].first == NULL) {
        parent[temp].first = 'S';
        parent[temp].second = now;
        q.push(temp);
    }
}
 
void L() {
    int temp = result.init[1];
    temp = temp * 10 + result.init[2];
    temp = temp * 10 + result.init[3];
    temp = temp * 10 + result.init[0];
 
    if (!visit[temp] && parent[temp].first == NULL) {
        parent[temp].first = 'L';
        parent[temp].second = now;
        q.push(temp);
    }
}
 
void R() {
    int temp = result.init[3];
    temp = temp * 10 + result.init[0];
    temp = temp * 10 + result.init[1];
    temp = temp * 10 + result.init[2];
 
    if (!visit[temp] && parent[temp].first == NULL) {
        parent[temp].first = 'R';
        parent[temp].second = now;
        q.push(temp);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> Testcase;
    while (Testcase--) {
        for (int i = 0; i < 10000; i++) parent[i].first = NULL;
        for (int i = 0; i < 10000; i++) visit[i] = 0;
 
        cin >> A >> B;
        q.push(A);
 
        while (!q.empty()) {
            now = q.front();
            q.pop();
 
            if (visit[now]) continue;
            visit[now] = true;
            
            if (now == B) {
                while (!q.empty()) q.pop();
                break;
            }
// now_check 를 통해서 구조체에 한자리씩 저장해둔다
            now_check(now);
// 주어진 조건에 맞게 함수내에서 q push
            D(), S(), L(), R();
        }
 
        int temp = B;
// 부모를 따라가는 과정
        while (parent[temp].first != NULL) {
            s.push(parent[temp].first);
            temp = parent[temp].second;
        }
        while (!s.empty()) {
            cout << s.top();
            s.pop();
        }
        cout << '\n';
    }
 
    return 0;
}
 
 
 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2251번 물통  (0) 2020.01.24
BOJ 1525번 퍼즐  (0) 2020.01.24
BOJ 1963번 소수 경로  (0) 2020.01.23
BOJ 13913번 숨바꼭질4  (0) 2020.01.23
BOJ 13549번 숨바꼭질3  (0) 2020.01.22

+ Recent posts

티스토리툴바