베르트랑 공준




소수를 에라토스테네스의 체를 사용해 판별해야 한다.

백준 1978 소수 찾기    (https://www.acmicpc.net/problem/1978)
백준 1929 소수 구하기 (https://www.acmicpc.net/problem/1929)


와 풀이를 겸한다.



에라토스테네의 체는 N보다 작거나 같은 모든 소수를 구하는 알고리즘이다.


방법은 다음과 같다.


2부터 시작하면서, 2의 모든 배수를 거른다.(2는 제외하고)


걸러지지 않은 가장 작은 수부터, 배수를 거르는 위의 작업을 반복한다.



위의 알고리즘은 N번 루프를 돌면서 배수들을 거른다.


루프 한 번당 배수들은 몇 개나 걸려질까?


위키신이 이르시길(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity)


평균적으로 log (log n) 번 걸러진다 하신다. 따라서 이 알고리즘의 시간복잡도는 n * log(log n) 이다.



베르트랑 공준은 임의의 n에 대해 (n, 2n] 구간엔 반드시 소수가 존재한다는 주장이다.


이를 검증하기 위해 여러 n이 주어지며, 매 번 소수의 갯수를 리턴해야 한다.


n이 몇 번이나 주어질지 상세되어있지 않으므로, 이미 부분합을 구해놓자.


그러면 n마다 psum[2 * n] - psum[n] 으로 (n, 2n]구간의 소수의 갯수를 선형시간에 알아낼 수 있다.



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
#include <stdio.h>
 
#define maxn 246912
int t;
 
bool is_not_prime[maxn + 1] = { true,true,false };
int psum[maxn + 1];
 
int main() {
    for (int i = 2; i <= maxn; ++i) {
        if (is_not_prime[i])
            continue;
        for (int j = i + i; j <= maxn; j += i)
            is_not_prime[j] = true;
    }
 
    for (int i = 2; i <= maxn; ++i) {
        psum[i] = psum[i - 1];
        if (!is_not_prime[i])
            psum[i]++;
    }
 
    while (1) {
        scanf("%d", &t);
        if (t == 0)
            break;
 
        printf("%d\n", psum[t * 2] - psum[t]);
    }
 
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10973 이전 순열  (0) 2017.09.11
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

화학식량




화학식이 주어지면, 식에 포함된 모든 원자들의 질량합을 구해야 한다.(이를 화학식량이라 한단다)

원자의 종류는 세 가지만 주어지며, 괄호에 곱해지는 숫자는 정수로 최대 9이다.



보통 괄호가 중첩되면서 안의 데이터를 가공해야 할 때 스택을 주로 쓰곤 한다.

따라서 재귀적으로 식을 가공하는 것과 동일하지만, 빡대가리는 재귀함수를 구성하는 것도 버겁기 때문에

한 글자 한 글자 보면서 스택을 채워보자.


글자들은 4가지로 분류할 수 있다.

1. 알파벳 2. 숫자 3. 여는 괄호 4. 닫는 괄호


여는 괄호(3)가 의미하는 바는, 이제 닫는 괄호(4)가 나올 때 까지 안의 작은 식을 계산해야 함을 의미한다.

자연스럽게 새로운 스택을 쌓으라는 뜻과 일치한다.

안의 식을 계산했다 치고 괄호의 끝이 나오면 어떻게 해야 할까? 더 이상의 작은 식은 없다는 뜻이니까

계산한 결과를 아래 스택에 더해주자. (POP하고 TOP에 더해준다)


문제는 숫자다. 닫는 괄호나 알파벳의 뒤엔 숫자가 올 수도 있고, 그렇다면 앞의 작은 식에 숫자를 곱해줘야 한다.

따라서 알파벳(1)이나 닫는 괄호(4)가 나올 때면, 뒤에 숫자가 올 수도 있으므로 임시변수에 결과를 기록해야 한다.

다행히 새로운 알파벳, 닫는 괄호가 연달아 나온다 해도 숫자는 작은 식 전체에 곱해지는 것이므로

인트형 변수 하나로 결과를 기록할 수 있다.


이제 케이스 별로 스택의 동작을 정의해보자.

1 -> 현재 TOP에 원자량을 더한다. 임시변수에 원자량을 저장한다.

3 -> 새로운 스택을 쌓고 0으로 초기화 한다.

4 -> 현재 TOP의 값을 임시변수에 저장하고 POP한다. 이 후 TOP에 결과를 더해준다.


2 -> 임시변수에 숫자를 곱해 TOP에 더해준다. 다만 1과 4에서 이미 TOP에 한 번 더해줬으므로 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
#include <stdio.h>
#include <string.h>
 
int stack[100], st_cnt, tmp;
char buf[101];
 
int main() {
    scanf("%s", buf);
    int l = strlen(buf);
 
    for (int i = 0; i < l; ++i) {
        char c = buf[i];
 
        if (c == 'H') {
            tmp = 1;
            stack[st_cnt] += 1;
        }
        else if (c == 'C') {
            tmp = 12;
            stack[st_cnt] += 12;
        }
        else if (c == 'O') {
            tmp = 16;
            stack[st_cnt] += 16;
        }
            
 
        else if (c == '(')
            stack[++st_cnt] = 0;
        else if (c == ')') {
            tmp = stack[st_cnt--];
            stack[st_cnt] += tmp;
        }
 
        else if ('1' < c && c <= '9')
            stack[st_cnt] += tmp * (c - '1');
    }
    printf("%d", stack[0]);
    return 0;
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 11003 최소값 찾기  (0) 2018.07.13
중위표기법을 후위표기법으로 바꿔서 계산하는 알고리즘  (0) 2018.02.22
백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22

휴대폰 자판




문자열들을 트라이로 저장해둔다.

탐색시마다 다음 트라이로 넘어갈 때 가능성이 하나 밖에 없으면 자동완성된다.

단 처음글자는 무조건 쳐야한다.



트라이에 딸린 트라이의 갯수를 알고, 빠르게 다음 트라이로 넘어가야 한다.


또한 자동완성여부를 판단하는데 있어서, 지금까지 지나온 트라이들이 다른 문자열을 포함하는지도 확인해야 한다.


hello의 경우 탐색하는데 l부터는 자식 트라이가 하나씩 밖에 없지만,


hell이란 다른 문자열이 먼저 끝나기 때문에 o를 추가로 쳐야 한다.



따라서 트라이 구조체에 문자열이 끝났는지를 판별하는 변수와, 자식 트라이의 수를 알려주는 변수를 추가한다.


탐색중에 버튼을 누르는 경우는 다음의 세가지다.


1. 처음 버튼을 누를 때


2. 자식 수가 2개 이상일 때


3. end를 지나칠 때



HELLO를 탐색할 때의 과정이다.


처음 버튼을 누를 때 +1


HE다음 자식이 두 개니까 +1


HELL이란 작은 문자열이 있었으니까 +1


총 3번 눌러야 한다.


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
#include <iomanip>
#include<iostream>
using namespace std;
 
#define alpha 26
#define maxn 100000
bool inital;
int ans, n;
char arr[maxn][81];
 
struct trie {
    trie* pan[alpha];
    bool end;
    int cnt;
 
    trie() {
        for (int i = 0; i < alpha; ++i)
            pan[i] = nullptr;
        end = false;
        cnt = 0;
    }
    ~trie() {
        for (int i = 0; i < alpha; ++i)
            if (pan[i] != nullptr)
                delete pan[i];
    }
 
    void insert(char* str) {
        if (*str == '\0') {
            end = true;
            return;
        }
            
 
        int cur = *str - 'a';
        if (pan[cur] == nullptr) {
            pan[cur] = new trie();
            cnt++;
        }
        pan[cur]->insert(str + 1);
    }
 
    void find(char* str) {
        if (*str == '\0')
            return;
 
        if (inital) {
            inital = false;
            ans++;
        }
        else {
            if (end)
                ans++;
            else if (cnt > 1)
                ans++;
        }
            
        int cur = *str - 'a';
        pan[cur]->find(str + 1);
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin>>n) {
        trie* root = new trie();
        ans = 0;
 
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
            root->insert(arr[i]);
        }
            
        for (int i = 0; i < n; ++i) {
            inital = true;
            root->find(arr[i]);
        }
 
        cout << fixed << setprecision(2)<< (double)ans / (double)n<<'\n';
        delete root;
 
    }
    return 0;
}
cs



'알고리즘 > Trie 트라이' 카테고리의 다른 글

백준) 5052 전화번호 목록  (0) 2018.01.29

전화번호 목록


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




트라이 구조체의 10칸짜리 숫자 판을 보면서, 중간에 끝나는 문자열이 삽입되었는지를 기억해야 한다.


따라서 구조체에 끝났는지 기억하는 변수를 추가해줘서, 삽입함수가 끝날 때 해당 구조체에 기록해둔다.



이제 모든 전화번호들을 트라이들을 헤집으면서 탐색할 때, 아직 전화번호가 끝나지 않았는데, 끝났다는 기록이 나오면


일관성 없는 목록임을 알 수 있다.





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
#include <stdio.h>
#define num 10
#define maxn 10000
 
struct trie {
    trie* pan[num];
    bool end;
 
    trie() {
        for (int i = 0; i < num; ++i)
            pan[i] = nullptr;
        end = false;
    }
    ~trie() {
        for (int i = 0; i < num; ++i)
            if (pan[i] != nullptr)
                delete pan[i];
    }
 
    void insert(char* str) {
        if (*str == '\0') {
            end = true;
            return;
        }
        //종료
        int cur = *str - '0';
        if (pan[cur] == nullptr)
            pan[cur] = new trie();
        pan[cur]->insert(str + 1);
    }
 
    int find(char* str) {
        if (*str == '\0')
            return 0;
 
        if (end)
            return 1;
 
        int cur = *str - '0';
        return pan[cur]->find(str + 1);
    }
};
 
int t, n;
char buf[maxn][11];
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
 
        trie* root = new trie();
 
        for (int i = 0; i < n; ++i) {
            scanf("%s", buf[i]);
            root->insert(buf[i]);
        }
        
        bool ans = true;
        for (int i = 0; i < n; ++i) {
            if (root->find(buf[i])) {
                ans = false;
                break;
            }
        }
        if (ans)
            puts("YES");
        else
            puts("NO");
 
        delete root;
    }
}
cs


'알고리즘 > Trie 트라이' 카테고리의 다른 글

백준) 5670 휴대폰 자판  (0) 2018.01.29

외계인의 기타 연주




6개의 줄을 가지고 연주를 하는데, 눌러야 하는 줄과 프렛의 번호가 주어진다.

이 때 이미 더 높은 프렛들을 누르고 있었다면 전부 띄어야 한다.

프렛을 누르거나 떼는 과정을 모두 카운트 할 때, 가장 카운트가 적은 방법은 무엇일까?



직관적으로 줄마다 스택으로 생각해서 풀었다.

1번 줄의 5, 7 ,9 를 누르고 있었다면, 1번 줄 스택엔 5, 7, 9가 쌓여있다. 

이 때 6을 누르라는 연주가 주어지면 7과 9를 pop하고 6을 push 한다. 따라서 3의 카운트가 증가한다.


어떤 최소화하려는 전략으로 5까지 떼버리고 6을 누르는 것은 최소의 전략이 아니기 때문이다.

5를 떼는 방법은 다음의 어떤 케이스가 들어와도 누르는 프렛을 유지하는 것보다 카운트가 더 높다.


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
#include <stdio.h>
#include <stack>
using namespace std;
 
int n, p, a, b, t, ans;
stack<int> sts[7];
 
int main() {
    scanf("%d %d", &n, &p);
    while (n--) {
        scanf("%d %d", &a, &b);
        while (1) {
            if (sts[a].empty()) {
                sts[a].push(b);
                ans++;
                break;
            }
            t = sts[a].top();
            if (b == t) {
                break;
            }
            else if (b > t) {
                sts[a].push(b);
                ans++;
            }
            else {
                sts[a].pop();
                ans++;
            }
        }
    }
    printf("%d", ans);
    return 0;
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

중위표기법을 후위표기법으로 바꿔서 계산하는 알고리즘  (0) 2018.02.22
백준) 2257 화학식량  (0) 2018.01.31
백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14

좋은 단어 




예제 입력 

3
ABAB
AABB
ABBA



같은 글자 두 개씩 쌍을 짓는데, 글자 위로만 선을 그어서 쌍을 지어야 한다.


이 선이 겹치지 않을 때 좋은 단어로 친다.


예제의 경우에 ABAB는 좋은 단어가 아니다.



퍼뜩 떠오른 생각은 스택에 넣으면서 최상위 글자랑 지금 넣는 글자랑 다르면 좋은 단어가 아니다.


따라서 첫 글자는 무조건 스택에 넣어야 한다.


두번째 글자부터 이를 확인해 주면된다.


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
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
 
int n, ans, len;
char buf[100001];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        len = strlen(buf);
        stack<char> st;
        st.push(buf[0]);
 
        for (int j = 1; j < len; ++j) {
            if (st.empty())
                st.push(buf[j]);
 
            else if (st.top() == buf[j])
                st.pop();
            else
                st.push(buf[j]);
        }
 
        if (st.empty())
            ans++;
    }
    printf("%d", ans);
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 2257 화학식량  (0) 2018.01.31
백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13

문자열 폭발 



상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이 때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.



문자열을 순회할때 폭발 문자열과 같은지 확인하고, 같다면 현재 보고 있는 인덱스를 다시 당겨서 정답을 채워나가자.


비슷한 문자가 나와서 같은지 확인할 때, 너무 앞에서 걸려서 처음 인덱스를 벗어나버리는 경우를 생각하지 못해 오래걸렸다.


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
#include <stdio.h>
#include <string.h>
using namespace std;
 
char buf[1000001];
char ans[1000001];
char ex[37];
 
int buf_len, ex_len;
 
int main() {
    scanf("%s %s", buf, ex);
 
    buf_len = strlen(buf);
    ex_len = strlen(ex);
 
    int p = 0;
    for (int i = 0; i < buf_len; ++i) {
        ans[p++] = buf[i];
 
        if (ans[p - 1] == ex[ex_len - 1]) {
            if (p - ex_len >= 0) {
                bool chk = false;
                for (int i = 0; i < ex_len; ++i) {
                    if (ans[p - 1 - i] != ex[ex_len - 1 - i]) {
                        chk = true;
                        break;
                    }
                }
 
                if (!chk) {
                    p -= ex_len;
                }
            }
        }
    }
    if (p == 0)
        printf("FRULA");
    else {
        ans[p] = '\0';
        printf("%s", ans);
    }
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 3986 좋은 단어  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 2110 공유기 설치  (0) 2018.01.09

Puyo Puyo




복잡한 구현의 문제.

우리가 아는 바로 그 게임을 구현하면 된다.

주의할 점은 현재 상태에서 4개이상 붙어버린 뿌요들은 한 번에 터지고(콤보 1),

한 번에 바닥으로 내려가고, 새로운 상태에서 새롭게 붙어버린 뿌요들도 한 번에 터진다는 것이다.



구현은 다음과 같이 하였다.


1. 맵을 DFS로 돌면서 현재 붙어버린 뿌요들을 파악한다.


2. 이 중 4개 이상되는 뿌요들만 한꺼번에 터진다.


3. 나머지 뿌요들이 바닥으로 내려오게 맵을 갱신해준다.


4. 1~3과정을 반복하면서 콤보 수를 센다.



과정 1을 수행하면서, 맵을 다른 곳에 기록해야 한다. DFS는 2개만 되어도 수행될 것이므로,


다른 곳에 좌표정보를 기록해두고, 과정 2에서 이를 써먹으면서 맵을 갱신해야 한다.



과정 3은 12*1의 배열이 6개 있다고 생각하고, 6개의 배열을 각각 갱신해주었다.


배열에서 뿌요들만 빼내서 다른 곳에 기록해두고, 배열을 갱신하는 방법을 사용했다.(스택 OR 큐)



코드로 옮기면 다음과 같다.


모든 과정을 수행하면서 맵 전체를 살피는게 불편하다면, 과정마다 뿌요들 중 최고 높이를 갱신하는 과정을 추가한다면


최적화가 가능해지지 않을까 생각한다.


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
#include <stdio.h>
#include <stack>
using namespace std;
 
typedef struct col {
    int x, y;
}col;
stack<col> st;
stack<int> st2;
 
int map[12][6];
int visit[12][6];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
char buf[8];
 
int dfs(int x, int y, int c) {
    int cnt = 1;
    visit[x][y] = c;
    st.push({ x,y });
 
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= 12 || yy >= 6)
            continue;
 
        if (map[xx][yy] == c && visit[xx][yy] == 0)
            cnt += dfs(xx, yy, c);
    }
    return cnt;
}
 
void arange() {
    for (int i = 0; i < 12; ++i)
        for (int j = 0; j < 6; ++j)
            visit[i][j] = 0;
 
    for (int i = 0; i < 6; ++i) {
        for (int j = 11; j >= 0; --j) {
            if (map[j][i] > 0) {
                st2.push({ map[j][i] });
                map[j][i] = 0;
            }
 
        }
        int cnt = 0;
        while (!st2.empty()) {
            map[cnt++][i] = st2.top();
            st2.pop();
        }
    }
}
 
int main() {
    for (int i = 11; i >= 0; --i) {
        scanf("%s", buf);
        for (int j = 0; j < 6; ++j) {
            if (buf[j] == 'R')
                map[i][j] = 1;
            else if (buf[j] == 'G')
                map[i][j] = 2;
            else if (buf[j] == 'B')
                map[i][j] = 3;
            else if (buf[j] == 'P')
                map[i][j] = 4;
            else if (buf[j] == 'Y')
                map[i][j] = 5;
        }
    }
 
    int combo = 0;
 
    while (1) {
        int del = 0;
        for (int i = 0; i < 12; ++i) {
            for (int j = 0; j < 6; ++j) {
                if (map[i][j] > 0 && visit[i][j] == 0) {
                    int cnt = dfs(i, j, map[i][j]);
 
                    if (cnt >= 4) {
                        del += cnt;
 
                        while (!st.empty()) {
                            map[st.top().x][st.top().y] = 0;
                            st.pop();
                        }
                    }
                    else {
                        while (!st.empty())
                            st.pop();
                    }
 
                }
            }
        }
        if (del == 0)
            break;
 
        arange();
        combo++;
    }
    printf("%d", combo);
 
    return 0;
}
cs



'알고리즘 > 미분류' 카테고리의 다른 글

백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 2110 공유기 설치  (0) 2018.01.09
백준) 1695 팰린드롬 만들기  (0) 2017.09.06

섬의 개수






유기농 배추(http://js1jj2sk3.tistory.com/71?category=725176)와 같은문제.

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
#include <stdio.h>
 
int map[50][50], w, h;
int dir[8][2] = { {1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1} };
 
void dfs(int x, int y) {
    map[x][y] = 0;
 
    for (int i = 0; i < 8; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= h || yy >= w)
            continue;
 
        if (map[xx][yy] == 1)
            dfs(xx, yy);
    }
}
 
int main() {
    while (1) {
        scanf("%d %d", &w, &h);
        if (w == 0 && h == 0)
            return 0;
 
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                scanf("%d", &map[i][j]);
 
        int cnt = 0;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (map[i][j] == 1) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
 
        printf("%d\n", cnt);
    }
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2615 오목  (0) 2018.02.06
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 1012 유기농 배추  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14
백준) 3055 탈출  (3) 2018.01.14

유기농 배추




DFS의 기본적인 버전이다.

재귀적으로 돌아가는 과정만 이해하면 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
#include <stdio.h>
 
int t;
int m, n, k;
int x, y;
int ans;
 
int map[50][50];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
 
void dfs(int x, int y) {
    map[x][y] = 0;
 
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= n || yy >= m)
            continue;
 
        if (map[xx][yy] != 1)
            continue;
 
        dfs(xx, yy);
    }
}
 
int main() {
    scanf("%d", &t);
 
    while (t--) {
        scanf("%d %d %d", &m, &n, &k);
 
        ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                map[i][j] = 0;
 
        for (int i = 0; i < k; ++i) {
            scanf("%d %d", &x, &y);
            map[y][x] = 1;
        }
 
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (map[i][j] == 1) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
            
 
        printf("%d\n", ans);
    }
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14
백준) 3055 탈출  (3) 2018.01.14
백준) 10216 Count Circle Groups  (0) 2017.10.09

+ Recent posts

티스토리툴바