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

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

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

 

간단한 BFS 문제입니다.

주의해야할 점이 있다면 건물은 1층부터 F 층까지 있다는 점으로

범위가 벗어나면 갈 수 없다는 점입니다

 

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
#include <iostream>
#include <queue>
using namespace std;
 
queue<pair<int, int> > q;
bool visit[1000001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    bool check = false;
    int f, s, g, u, d;
    cin >> f >> s >> g >> u >> d;
 
    q.push({ s,0 });
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (now > f) continue;
        if (now < 1) continue;
        if (visit[now]) continue;
        visit[now] = true;
 
        if (now == g) {
            cout << cnt;
            check = true;
            break;
        }
 
        if (u)q.push({ now + u, cnt + 1 });
        if (d)q.push({ now - d, cnt + 1 });
    }
 
    if (!check) cout << "use the stairs";
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2661번 좋은수열  (0) 2020.01.31
BOJ 1759번 암호 만들기  (0) 2020.01.31
BOJ 3108번 로고  (0) 2020.01.31
BOJ 2186번 문자판  (0) 2020.01.27
BOJ 2251번 물통  (0) 2020.01.24

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

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

 

이 문제를 푸는 요령은 2가지가 있습니다.

 

1) BFS 또는 DFS 를 이용해서 한붓그리기를 코드

2) 애초에 사각형이 겹치는 부분에 대한 탐색을 하면되니 DFS 를 이용한 사각형의 겹침 부분을 코드

 

1번으로 풀다가 틀려서 2번으로 방법을 변경하였습니다.

check_box() 에 대해서 설명해보자면

check_box() 는 사각형이 겹치는지 안겹치는지 판단하는 함수로,

false 를 반환할 때 겹친다라고 가정하였습니다.

 

lx[a] < fx[b] || ly[a] < fy[b] 의 부분은 두 사각형이 아예 떨어져있는 경우로

true 를 반환하게 되어, 사각형이 겹치지 않는다를 의미하게 됩니다.

fx[a] > fx[b] && lx[a] < lx[b] && fy[a] > fy[b] && ly[a] < ly[b] 의 부분은

한 사각형이 다른 사각형을 포함하고 있음을 나타내는 경우로

true 를 반환하게 되어, 사각형이 겹치지 않는다를 의미하게 됩니다.

 

둘다 만족하지 않아 false 를 반환하게 되는 경우는 무조건 사각형이 겹치게 됨을 의미하게 되어,

다른 사각형을 확인하게 되는 dfs() 로 진입하게 됩니다.

 

문제의 중요한 부분은 (0,0) 부터 탐색을 시작해야한다는 것이고,

이를 위해서 반복문을 0<=N 으로 작성하였습니다.

일부러 cin >> +1 해가면서 좌표를 받은 이유도 첫 좌표는 (0,0),(0,0) 이라는 점(사각형이 됩니다)을 사용하기

위해서 입니다.

 

마지막에 ans-1 의 -1 을 해준 이유 역시 반복문은 최소 1번이상 실행되게 되어있는데

(0,0) 에 걸치는 사각형이 존재할 수 있기 때문입니다.

 

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
#include <iostream>
using namespace std;
#pragma warning(disable:4996)
 
int N;
int fy[1001], fx[1001], lx[1001], ly[1001];
bool visit[1001];
 
bool check_box(int a, int b) {
    return (lx[a] < fx[b] || ly[a] < fy[b] || fx[a] > fx[b] && lx[a] < lx[b] && fy[a] > fy[b] && ly[a] < ly[b]);
}
 
void dfs(int now) {
 
    visit[now] = true;
    for (int i = 0; i <= N; i++) {
        if (visit[i]) continue;
        if (!check_box(now,i) && !check_box(i,now)) {
            dfs(i);
        }
    }
 
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    bool temp = false;
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> fx[i+1] >> fy[i+1] >> lx[i+1] >> ly[i+1];
    }
 
    int ans = 0;
    
    for (int i = 0; i <= N; i++) {
        if (visit[i]) continue;
        ans++;
        dfs(i);
    }
 
    cout << ans - 1;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1759번 암호 만들기  (0) 2020.01.31
BOJ 5014번 스타트링크  (0) 2020.01.31
BOJ 2186번 문자판  (0) 2020.01.27
BOJ 2251번 물통  (0) 2020.01.24
BOJ 1525번 퍼즐  (0) 2020.01.24

+ Recent posts

티스토리툴바