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

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

 

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
#include <iostream>
using namespace std;
 
int R, C, Max;
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
char arr[20][20];
bool visit[26];
 
void dfs(int y, int x, int cnt) {
    
    Max = Max < cnt ? cnt : Max;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + my[i];
        int xx = x + mx[i];
        if (yy >= 0 && yy < R && xx >= 0 && xx < C && !visit[arr[yy][xx]-'A']) {
            visit[arr[yy][xx] - 'A'] = true;
            dfs(yy, xx, cnt + 1);
            visit[arr[yy][xx] - 'A'] = false;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cin >> arr[i][j];
 
    visit[arr[0][0] - 'A'] = true;
    dfs(0, 0, 1);
    cout << Max;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1806번 부분합  (0) 2020.01.31
BOJ 2003번 수들의 합2  (0) 2020.01.31
BOJ 2580번 스도쿠  (0) 2020.01.31
BOJ 2661번 좋은수열  (0) 2020.01.31
BOJ 1759번 암호 만들기  (0) 2020.01.31

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

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

 

하나의 실수때문에 2시간이나 날린 문제입니다.. 흑

 

스도쿠를 풀기위한 기본 접근방법은 가로,세로,3*3사각 을 탐색하는것이 아닌

가로,세로,3*3사각 에 맞는 배열을 이용하는 것입니다.

주구장창 탐색만 했다가는 TLE 에 걸립니다.

 

가로, 세로, 9개의 사각형에 대한 사용배열을 미리 만들어두고, dfs 를 통해서 

백트래킹을 하듯이 일단 넣어보고 안되면 리턴하고 이런식으로 코드해주시면 됩니다.

 

가로는 arr 배열의 행 인덱스를 이용해서 row[9][10]; 으로 

세로는 arr 배열의 열 인덱스를 이용해서 col[9][10]; 으로

3*3 사각은 3*3 의 9개 구간을 0,0 0,1 0,2 1,0 1,1 ... 이런식으로 총 3*3 개로 나눈 3차원 visit[3][3][10] 을 사용했습니다

 

실수했던 것은 dfs (int y, int x) 를 받아서 y,x 를 <9 에 해당하는 범위내로 2중포문 돌듯이 구현하였는데

int i = y, ... int j = x 로 하다보니

i 가 다음행으로 증가할때 j 는 0부터 시작해야되는데 x부터 시작하게되는.. 비참한 실수를 하고 말았습니다.

 

이상하게 문제의 예제나 게시판의 반례들은 잘 돌아가길래 결국 처음부터 다시 읽어보니 찾을 수 있었습니다.

좀 더 꼼꼼해야함을 배우고 가는 문제였습니다..

 

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
#include <iostream>
 
using namespace std;
 
int arr[9][9];
bool row[9][10];
bool col[9][10];
bool visit[3][3][10];
 
bool check(int i, int j, int k) {
    if (row[i][k]) return false;
    if (col[j][k]) return false;
    if (visit[i / 3][j / 3][k]) return false;
 
    return true;
}
 
bool dfs(int y, int x) {
 
    for (int i = y; i < 9; i++) {
        for (int j = x; j < 9; j++) {
            if (!arr[i][j]) {
                bool temp = false;
                for (int k = 1; k <= 9; k++) {
                    if (check(i, j, k)) {
                        temp = true;
                        arr[i][j] = k;
                        row[i][k] = col[j][k] = visit[i / 3][j / 3][k] = true;
                        if (j < 8) temp = dfs(i, j + 1);
                        else temp = dfs(i + 1, 0);
 
                        if (!temp) {
                            arr[i][j] = 0;
                            row[i][k] = col[j][k] = visit[i / 3][j / 3][k] = false;
                            temp = false;
                        }
                    }
                    if (temp) break;
                }
                if (!temp) return false;
            }
        }
        x = 0;
    }
 
    return true;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    for (int i = 0; i < 9; i++) {
        for (int k = 0; k < 9; k++) {
            cin >> arr[i][k];
            if (arr[i][k]) row[i][arr[i][k]] = true, col[k][arr[i][k]] = true, visit[i / 3][k / 3][arr[i][k]] = true;
        }
    }
 
    bool temp = dfs(0, 0);
 
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2003번 수들의 합2  (0) 2020.01.31
BOJ 1987번 알파벳  (0) 2020.01.31
BOJ 2661번 좋은수열  (0) 2020.01.31
BOJ 1759번 암호 만들기  (0) 2020.01.31
BOJ 5014번 스타트링크  (0) 2020.01.31

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

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

 

코드에 대한 설명은 주석처리해놓았습니다.

현재 스트링으로 좋은수열인지 확인하기 위한 2개의 스트링을 만들어서

좋은수열의 조건을 만족한다면 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
#include <iostream>
#include <string>
using namespace std;
 
int N;
bool ans = false;
char arr[4] = { '0','1','2','3' };
 
// 좋은수열인지 확인
// 길이는 1부터 2배씩 늘어나고 그 길이가 스트링의 길이를 만족할때 까지만 탐색한다.
// 2개의 스트링을 만들어서 비교시 나쁜수열이라면 false 를 반환
bool check(string str, int idx) {
    string str1, str2;
    for (int i = str.size() - idx; i < str.size(); i++)
        str1 += str[i];
    for (int i = str.size() - (idx * 2); i < str.size() - idx; i++)
        str2 += str[i];
 
    if (str1.compare(str2) == 0) return false;
 
    return true;
}
 
void dfs(string str) {
    if (ans) return;
    if (str.size() == N) {
        cout << str;
        ans = true;
        return;
    }
 
    for (int i = 1; i <= 3; i++) {
        bool temp = true;
        for (int k = 1; k * 2 <= str.size() + 1; k++) {
            if (!check(str + arr[i], k)) {
                temp = false;
                break;
            }
        }
        // 좋은수열의 조건을 만족한다면 dfs
        if (temp) dfs(str + arr[i]);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
 
    // 맨 앞자리는 1일때가 가장 작다
    dfs("1");
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1987번 알파벳  (0) 2020.01.31
BOJ 2580번 스도쿠  (0) 2020.01.31
BOJ 1759번 암호 만들기  (0) 2020.01.31
BOJ 5014번 스타트링크  (0) 2020.01.31
BOJ 3108번 로고  (0) 2020.01.31

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

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

 

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
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
#define endl "\n"
 
char arr[15];
int L, C;
 
void dfs(string str, int ja, int mo, int idx) {
    if (str.size() == L) {
        if (ja < 2 || mo < 1) return;
        cout << str << endl;
    }
 
    for (int i = idx; i < C; i++) {
        if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
            dfs(str + arr[i], ja, mo + 1, i + 1);
        else
            dfs(str + arr[i], ja + 1, mo, i + 1);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> L >> C;
 
    for (int i = 0; i < C; i++) cin >> arr[i];
 
    sort(arr, arr + C);
 
    // 알아야하는 정보
    // 현재 스트링, 자음 갯수, 모음 갯수, 현재 인덱스
    dfs("", 0, 0, 0);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2580번 스도쿠  (0) 2020.01.31
BOJ 2661번 좋은수열  (0) 2020.01.31
BOJ 5014번 스타트링크  (0) 2020.01.31
BOJ 3108번 로고  (0) 2020.01.31
BOJ 2186번 문자판  (0) 2020.01.27

+ Recent posts

티스토리툴바