벽 부수고 이동하기




지도가 제공되고 최단 경로의 길이를 구하는 문제다.

벽을 한 개는 부술 수 있다는 추가 조건이 있긴 하지만, 최단 경로 문제니까 BFS로 풀어보자.


BFS는 완전탐색 알고리즘이므로, 잘만 하면 벽을 전부 하나씩 부수고 탐색하는 케이스들도 전부 탐색할 수 있다.

평행세계를 생각해보면 좋은데, 여기서 벽을 부술지 돌아갈지를 두 차원으로 나눠서 생각하는 것이다.

그러면 부순 세계와 돌아간 세계는 독립되고 서로 영향을 주지 않는다.


이를 구현하기 위해, BFS에서 주로 쓰는 VISIT배열을 삼차원으로 만든다.

즉, 이차원 배열이 두 개 쌓인 것이다. 기본적으론 벽을 부수지 않은 세계에서 출발하며,

벽을 만날 시에 벽을 부수고 다른 세계로 넘어가는 경우와, 벽을 돌아서 가는 경우를 모두 큐에 넣으면 된다.

이 후의 탐색은 개별적으로 진행된다.


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


STL을 쓰지 않아 코드가 매우 길다.


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
#include <stdio.h>
 
typedef struct col {
    int x, y, z;
};
col que[2000000];
int que_front, que_back;
#define que_size 2000000
void que_push(int x, int y, int z) {
    que[que_back] = { x,y,z };
    que_back = (que_back + 1) % que_size;
}
col que_pop() {
    col tmp = que[que_front];
    que_front = (que_front + 1) % que_size;
 
    return tmp;
}
int abs(int x) {
    return x > 0 ? x : -x;
}
 
int n, m;
char buf[1001];
int map[1000][1000];
int visit[1000][1000][2];
int dir[4][2] = { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
 
void bfs(int x, int y, int z) {
    que_push(x, y, z);
    visit[x][y][0] = 1;
 
    int cnt = 2;
    while (que_front != que_back) {
 
        int size = abs(que_front - que_back);
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4; ++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
                int zz = tmp.z;
 
                if (xx < 0 || yy < 0 || xx >= n || yy >= m)
                    continue;
 
                if (visit[xx][yy][zz])
                    continue;
 
                if (map[xx][yy] == 0) {
                    que_push(xx, yy, zz);
                    visit[xx][yy][zz] = cnt;
                }
 
                if (map[xx][yy] == 1) {
                    if (zz == 1)
                        continue;
                    else {
                        que_push(xx, yy, 1);
                        visit[xx][yy][1] = cnt;
                    }
                }
            }
        }
        cnt++;
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < m; ++j)
            map[i][j] = buf[j] - '0';
    }
 
    bfs(0, 0, 0);
 
    int ans1 = visit[n - 1][m - 1][0];
    int ans2 = visit[n - 1][m - 1][1];
 
    if (ans1 == 0 && ans2 == 0)
        printf("-1");
    else if (ans1 == 0)
        printf("%d", ans2);
    else if (ans2 == 0)
        printf("%d", ans1);
    else
        printf("%d", ans1 < ans2 ? ans1 : ans2);
 
    return 0;
}
cs


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

백준) 4963 섬의 개수  (0) 2018.01.14
백준) 1012 유기농 배추  (0) 2018.01.14
백준) 3055 탈출  (3) 2018.01.14
백준) 10216 Count Circle Groups  (0) 2017.10.09
백준) 2606 바이러스  (0) 2017.10.09

탈출




물이 인접한 칸으로 계속 불어날 때, 고슴도치가 물에 닿지 않고 목표지점까지 갈 수 있는지,

간다면 최단거리는 몇인지 알아내야 한다.


그래프 탐색문제이며, 최단거리를 알아내야 하므로 BFS를 써보기로 했다.

물과 고슴도치를 모두 큐에 넣고 BFS를 돌려버릴 수 있겠다.

하지만 둘 다 같은 시간에 같은 칸에 도착한다면 물이 이기는 경우를 처리할 수 없다.(내 생각에는)


그래서 물은 고슴도치의 이동에 전혀 영향을 받지 않으므로,

물만 BFS를 먼저 돌려서 언제 어디까지 불어나는지를 먼저 확인하자.

이 후 고슴도치는 물이 어떻게 불어나는지 저장된 지도를 보고 도착지점까지 BFS로 도착하면 된다.


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

요새 STL을 쓰지 않는 연습을 하고 있는지라, 코드가 매우 길다.


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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>
 
typedef struct col {
    int x, y;
}col;
 
col que[10000];
int que_front, que_back;
#define que_size 10000
void que_push(int x, int y) {
    que[que_back] = { x,y };
    que_back = (que_back + 1) % que_size;
}
col que_pop() {
    col tmp = que[que_front];
    que_front = (que_front + 1) % que_size;
 
    return tmp;
}
 
char buf[51];
int r, c;
int map[50][50];
int waters_cnt;
col waters[2500];
col start, dst;
 
int dir[4][2] = { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
int abs(int x) {
    return x > 0 ? x : -x;
}
 
void water_bfs() {
    int cnt = 2;
 
    while (que_front != que_back) {
        int size = abs(que_back - que_front);
 
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4; ++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
 
                if (xx < 0 || yy < 0 || xx >= r || yy >= c)
                    continue;
 
                if (map[xx][yy] != 0)
                    continue;
 
                que_push(xx, yy);
                map[xx][yy] = cnt;
            }
        }
        cnt++;
    }
}
 
int beaber_bfs() {
    int cnt = 2;
 
    while (que_front != que_back) {
        int size = abs(que_front - que_back);
 
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4; ++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
 
                if (xx < 0 || yy < 0 || xx >= r || yy >= c)
                    continue;
 
                if (xx == dst.x && yy == dst.y)
                    return cnt;
 
                if (map[xx][yy] == 0) {
                    que_push(xx, yy);
                    map[xx][yy] = -1;
                    continue;
                }
 
                if (map[xx][yy] == -1)
                    continue;
 
                if (map[xx][yy] <= cnt)
                    continue;
 
                que_push(xx, yy);
                map[xx][yy] = -1;
            }
        }
 
        cnt++;
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &r, &c);
 
    for (int i = 0; i < r; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < c; ++j) {
            if (buf[j] == '.') // 길
                continue;
            else if (buf[j] == 'D') { // 비버굴
                dst = { i,j };
                map[i][j] = -1;
            }
            else if (buf[j] == 'S') { // 고슴도치
                start = { i,j };
            }
            else if (buf[j] == 'X') // 돌
                map[i][j] = -1;
            else { // 물 
                waters[waters_cnt++] = { i,j };
                map[i][j] = 1;
            }
        }
    }
 
    //물이 번지는 시간 기록
    for (int i = 0; i < waters_cnt; ++i)
        que_push(waters[i].x, waters[i].y);
    water_bfs();
 
 
    map[start.x][start.y] = -1;
    que_push(start.x, start.y);
    
    int ans = beaber_bfs();
    if (ans == -1)
        printf("KAKTUS");
    else
        printf("%d\n", ans - 1);
 
    return 0;
}
cs


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

백준) 1012 유기농 배추  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14
백준) 10216 Count Circle Groups  (0) 2017.10.09
백준) 2606 바이러스  (0) 2017.10.09
백준) 2178 미로 탐색  (3) 2017.10.09

키로거




입력 케이스는 캐릭터와 좌우 화살표, 백스페이스로 분류된다.


캐릭터를 제외한 추가 키 들에 대한 기능을 정의해야 하는데,


좌우 화살표의 입력은 문자열 자체를 변경하진 않고 캐릭터가 입력될 위치(커서)를 바꾼다.


백스페이스는 현재 커서 바로 앞의 캐릭터를 지워야 한다.



위와 같은 기능을 구현하기 위해,


커서의 앞뒤를 구분하면서, 부가 키의 입력 시에 빠른 결과를 리턴해줄 구조를 짜야 하는데,


이를 스택으로 구현한다면 선형시간에 모든 기능이 수행된다.



커서의 앞과 뒤를 두 개의 스택으로 생각한다면


캐릭터의 입력은 앞의 스택에 push,


왼쪽 화살표는 앞 스택에서 pop -> 뒤 스택에 push,


반대로 오른쪽 화살표는 뒤 스택에서 pop -> 앞 스택에 push,


백스페이스는 앞 스택에서 pop


으로 구현할 수 있다.



기타 예외처리를 추가한 코드는 다음과 같다.


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
#include <stdio.h>
 
int T;
char buf[1000001];
int len;
int strlen(char buf[]) {
    int cnt = 0;
    while (buf[cnt] != '\0')
        cnt++;
    return cnt;
}
 
char stack1[1000001];
char stack2[1000001];
int stack1_size;
int stack2_size;
 
void stack_push(char stack[], char c, int& size) {
    stack[size++] = c;
}
char stack_pop(char stack[], int& size) {
    return stack[--size];
}
 
int main() {
    scanf("%d", &T);
 
    while (T--) {
        scanf("%s", buf);
        len = strlen(buf);
 
        for (int i = 0; i < len; ++i) {
            if (buf[i] == '<') {
                if (stack1_size == 0)
                    continue;
 
                stack_push(stack2, stack_pop(stack1, stack1_size), stack2_size);
            }
            else if (buf[i] == '>') {
                if (stack2_size == 0)
                    continue;
 
                stack_push(stack1, stack_pop(stack2, stack2_size), stack1_size);
            }
            else if (buf[i] == '-') {
                if (stack1_size == 0)
                    continue;
 
                stack_pop(stack1, stack1_size);
            }
            else
                stack_push(stack1, buf[i], stack1_size);
        }
 
        for (int i = 0; i < stack1_size; ++i)
            printf("%c", stack1[i]);
        for (int i = stack2_size-1; i >= 0; --i)
            printf("%c", stack2[i]);
        putchar('\n');
 
        stack1_size = 0;
        stack2_size = 0;
    }
 
    return 0;
}
cs


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

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

합이 0인 네 정수




크기가 N으로 같은 정수형 배열 네 개가 주어질 때,


각 배열의 원소를 하나 씩 골라서 더했을 때 0을 만들 수 있는 경우가 얼마나 되는지 계산해야 한다.



모든 경우를 시도해보고 0인 가짓수를 세 보면 가능하지만, 


N이 최대 사천이므로 N^4 으로 시간초과가 날 것이므로, 불가능함이 자명한 경우를 추리는 최적화가 필요하다.



예를 들어 세 정수의 합이 300 인데, 나머지 한 배열의 원소 중에 임의의 수를 더해봤더니 0보다 작다면,


그 수보다 작은 원소들은 시도해볼 필요가 없다.



따라서 이분 탐색을 통해 시간복잡도를 줄이기로 한다.


세 배열을 모두 더해보고 남은 한 배열에서 찾는다면 4000^3의 계산과정이 필요하다.


하지만 두 배열 씩 더해서 새로운 배열 두 개를 만들고, 한쪽 배열의 모든 원소를 다른 배열에서 이분탐색한다면,


새로운 배열 생성에 2 * 4000 ^ 2 만큼 걸리고, 남은 이분 탐색에선 4000 ^ 2 * log (4000 ^ 2) 만큼 걸린다.



주의할 점은, 중복의 경우를 세야 한다는 것이다.


예를 들어 한 쪽 배열에서 -40이란 원소에 의해 다른 배열에서 40을 찾는 경우에, 40은 중복해서 존재할 수 있다.


 

찾는 값은 lower_bound와 upper_bound의 차이 만큼 중복으로 존재한다.


만약 두 함수의 결과에 차이가 없다면, 다음 원소의 탐색시엔 upper_bound부터 탐색해도 무방하다.


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


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 <stdio.h>
#include <algorithm>
using namespace std;
 
int n, nn;
int ab[16000000], cd[16000000];
int a[4000], b[4000], c[4000], d[4000];
 
 
int main() {
    scanf("%d", &n);
    nn = n*n;
 
    for (int i = 0; i < n; ++i)
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ab[n*i + j] = -(a[i] + b[j]);
            cd[n*i + j] = c[i] + d[j];
        }
    }
 
    sort(cd, cd + nn);
 
    int left = 0, right = nn;
    long long ans = 0;
 
    for (int i = 0; i < nn; ++i) {
 
        while (left < right) {
            int mid = (left + right) / 2;
 
            if (ab[i] > cd[mid])
                left = mid + 1;
            else
                right = mid;
        }
 
        int lo = right;
        //int lo2 = lower_bound(cd, cd + nn, ab[i]) - cd;
 
        left = 0, right = nn;
        
        while (left < right) {
            int mid = (left + right) / 2;
 
            if (ab[i] >= cd[mid])
                left = mid + 1;
            else
                right = mid;
        }
 
        int hi = right;
        //int hi2 = upper_bound(cd, cd + nn, ab[i]) - cd;
 
        ans += (long long)(hi - lo);
 
        left = 0, right = nn;
    }
 
    printf("%lld", ans);
 
    return 0;
}
cs


'알고리즘 > 이진 탐색' 카테고리의 다른 글

백준) 1654 랜선 자르기  (2) 2018.01.09
백준) 2805 나무 자르기  (2) 2018.01.09

공유기 설치




N개 집의 위치가 일직선 상에 주어지고, 공유기의 갯수 C가 주어진다.

공유기는 집에만 설치 할 수 있을 때, C개를 적절하게 모두 설치하고자 한다.

이 때 설치 가능한 경우들 가운데, 가장 인접한 공유기 쌍의 거리는 최대 몇 까지 가능할까?


C가 2개라고 생각해본다면, 최인접 공유기 쌍간 거리는 시작집과 끝집 사이의 거리다.

C가 3개일 때 부터 고민을 해봐야 하는데, 모든 설치 가능한 경우를 시뮬레이션할 수 도 있다.

하지만 시간이 부족하므로 어떠한 최적화가 필요하다.


만약 최대거리가 x가 되게 시도해보고 성공한다면, x보다 작은 거리는 시도 해볼 필요가 없다.

따라서 이분탐색을 생각해 볼 수 있고, 집의 좌표는 최소 1, 최대 10억 이므로 log로 따지면 30번 안에 찾을 수 있다.


시도하는 과정은 어떻게 구현해야 할까?

그리디적으로 생각해보면 간략히 구현할 수 있다.

만약 중간 집들을 이용했을 때 현재 시도하는 거리가 유효하다면,

당연히 중간 집들의 맨 처음 집 대신 처음 집에 공유기를 심어도 유효하다는 사실은 변하지 않는다. 


만약 중간 집들 중 처음 집이 가장 인접한 공유기 쌍 중에 하나 였다면, 오히려 최대 길이는 늘어날 가능성이 있다.

아니었다면 최대 길이는 그대로 있다.

유효한 시뮬레이션임은 변하지 않는다.


따라서 우리는 처음 집에 공유기를 설치하고 나머지 과정을 시뮬레이션 하면 된다.

다음 집들을 살펴보면서 현재 시도하고 있는 최대길이를 유효하게만 해준다면 공유기를 심어도 되는 것이다.


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



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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, c;
int home[200000];
 
bool chk(int mid) {
    int cnt = 1;
    int cur = 0;
    int next = 1;
    
    while (next <= n - 1) {
        if (home[next] - home[cur] < mid)
            next++;
        else {
            cnt++;
 
            if (cnt == c)
                return true;
 
            cur = next;
            next = cur + 1;
        }
    }
    
    return false;
}
 
int main() {
    scanf("%d %d", &n, &c);
 
    for (int i = 0; i < n; ++i)
        scanf("%d", &home[i]);
        
    sort(home, home + n);
 
    int left = 1, right = home[n - 1] - home[0];
    int ans = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (ans < mid)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


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

백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 1695 팰린드롬 만들기  (0) 2017.09.06

랜선 자르기


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



나무 자르기(http://js1jj2sk3.tistory.com/64?category=749321)와 비슷한 문제다.


K개의 랜선을 적절하게 같은 길이로 잘라 N개의 랜선을 만들어야 하는데,


N개를 만들지 못하는 경우는 없다고 주어졌다.



길이는 모두 정수 값이므로, 나무 자르는 문제와 같이 가능한 모든 길이를 시도해 보면 된다.


마찬가지로 이분 탐색으로 범위를 줄여나갈 수 있고, 현재 시도 중인 길이에 대해 두 가지 케이스가 발생한다.



1. 잘라봐도 N개를 만들지 못할 때


더 긴 길이로 잘라봐야 만들지 못할것이 자명하므로 왼쪽 부분으로 좁혀서 탐색한다.


2. N개를 만들 수 있을 때


더 긴길이를 시도해 봐야 하므로 오른쪽 부분으로 좁혀서 탐색한다.



범위를 좁히다 보면 하한선과 상한선이 엇나가게 될 것이고, 중간에 기록해둔 값들 중 최대 길이가 정답이 된다.


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



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
#include <stdio.h>
using namespace std;
 
int k, n;
int lan[10000];
 
bool chk(int mid) {
    int cnt = 0;
 
    for (int i = 0; i < k; ++i)
        cnt += lan[i] / mid;
 
    return cnt >= n;
}
 
int main() {
    scanf("%d %d", &k, &n);
 
    int max = 0;
    for (int i = 0; i < k; ++i) {
        scanf("%d", &lan[i]);
        if (max < lan[i])
            max = lan[i];
    }
    
    long long left = 1, right = max;
    int ans = 0;
 
    while (left <= right) {
        long long mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (mid > ans)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


left를 초기화 할 때 1이 아닌 0으로 한다면 mid가 0이 되버려 런타임 오류가 발생할 수도 있다.

'알고리즘 > 이진 탐색' 카테고리의 다른 글

백준) 7453 합이 0인 네 정수  (0) 2018.01.10
백준) 2805 나무 자르기  (2) 2018.01.09

나무 자르기

 

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

 

 

시도해 볼 수 있는 높이는 모두 정수다.

 

따라서 모든 가능한 정수에 대해서 시도해보면, M보다 크거나 같은 결과가 나오는 높이들을 파악할 수 있고,  그 중 가장 큰 정수를 찾으면 된다.

 

 

하지만 모든 정수를 시도해 볼 필요는 없다.

 

만약 300의 높이로 시도해 보았을 때, M보다 작은 결과가 나온다면, 300보다 높은 높이로 시도했을 때도 당연히 실패할 것이기 때문이다.

 

 

따라서 가능한 결과들은 한 구간으로만 나올 것이다.

 

우리가 할 것은 그 구간을 빠르게 찾는 것이다.

 

 

이진 탐색으로 빠르게 구간을 찾을 수 있다. 

 

1/2 씩 구간을 줄여나가는 방벙으로, n개의 수를 로그시간에 탐색할 수 있다.

 

 

정수의 범위는 1부터 가장 높은 나무의 높이 까지다.

 

주어진 나무 높이의 합이 M보다 크다는 조건 때문에 1을 계산해볼 필요가 없다.

 

가장 큰 높이로 자르면 당연히 합이 0일 것이므로 계산해볼 필요가 없다.

 

 

이제부터 중간값으로 구간을 줄여보자.

 

중간 높이로 자르고 나면 두 가지 경우가 생긴다.

 

 

1. 잘린 나무의 합이 M보다 작을 경우

 

현재 높이보다 낮은 높이로 시도해 보아야 한다. 왼쪽 구간으로 변경

 

2. 잘린 나무의 합이 M보다 작거나 클 경우

 

현재 높이보다 높은 높이로 시도해 볼 수 있다. 오른쪽 구간으로 변경

 

 

이를 반복하다보면 구간의 제일 큰 정수 값을 알 수 있다.

 

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

 

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
#include <stdio.h>
using namespace std;
 
int n, m;
long long tree[1000000];
 
bool chk(int mid) {
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        if (mid < tree[i])
            sum += tree[i] - mid;
    }
 
    return sum >= m;
}
 
int main() {
    scanf("%d %d", &n, &m);
 
    int max = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &tree[i]);
        if (tree[i] > max)
            max = tree[i];
    }
 
 
    int left = 0, right = max;
    int ans = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (ans < mid)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}
 cs

 

나무의 높이들을 저장하는 배열을 정렬해 둔다면, 정수 값을 1씩 옮기지 않고 구간을 옮길 수 있으므로

 

최적화가 가능할 것 같다.

 

'알고리즘 > 이진 탐색' 카테고리의 다른 글

백준) 7453 합이 0인 네 정수  (0) 2018.01.10
백준) 1654 랜선 자르기  (2) 2018.01.09

Count Circle Groups

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






1. 접근


캠프들 끼리는 통신영역에 따라 한 그룹이 될 수도 안될 수도 있다.


그래프에서 총 그룹은 몇개나 나올까?


그래프는 n^2 에 만들 수 있을 것이다. 서로서로 비교해가면서 간선을 만들어준다.


그러고 나면 그래프에서 그룹이 총 몇개 있는지 찾는 법은 디스조인트-셋 이나 BFS / DFS 로 조질 수 있다.



2-1) 풀이 1


그래프에 대해 DFS로 그룹이 몇 개 있는지 셀 수 있을 것이다. 


visit을 확인해가면서 모든 캠프에 대해 DFS()를 호출해버린다.


간선이 N^2 개니까, 따라서 모든 캠프 N * DFS의 시간복잡도 (N + N^2) -> N^3 이나 걸린다.



2-2) 코드


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
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
using namespace std;
 
int t, n;
int camp[3000][3];
int visit[3000];
vector<vector<int>> map;
 
int dfs(int x) {
    int cnt = 1;
    visit[x] = 1;
 
    for (auto a : map[x]) {
        if (visit[a])
            continue;
        cnt += dfs(a);
    }
    return cnt;
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        map.clear();
        memset(visit, 0, sizeof(visit));
 
        scanf("%d", &n);
        map.resize(n);
 
        for (int i = 0; i < n; ++i)
            scanf("%d %d %d", &camp[i][0], &camp[i][1], &camp[i][2]);
 
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int x = camp[i][0] - camp[j][0];
                int y = camp[i][1] - camp[j][1];
                double r = (double)camp[i][2] + (double)camp[j][2];
                double d = sqrt(x*x + y*y);
 
                if (d <= r) {
                    map[i].push_back(j);
                    map[j].push_back(i);
                }
            }
        }
 
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (visit[i])
                continue;
 
            cnt++;
            for (auto v : map[i])
                dfs(v);
        }
 
        printf("%d\n", cnt);
    }
    return 0;
}
cs



3-1) 풀이 2


사실 집합이 몇개나 생기는지 세기만 하면 된다. 집합에 몇개나 들어있는지 알 필요가 없다


그러면 각 노드에 대해 그래프를 만들면서 동시에 두 노드간 부모가 다르면(find) 집합을 만들어 버릴 수 있다.(merge)


처음의 각 노드가 하나의 집합이었다면, merge를 할 수록 집합 갯수는 줄어든다.



디스조인트 셋은 선형시간에 연산하므로 이 방법은 N^2 이다.



3-2) 코드


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
#include <stdio.h>
#include <math.h>
using namespace std;
 
int t, n;
int camp[3000][3];
int parent[3000];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
 
    if (x == y)
        return;
    else
        parent[x] = y;
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d %d %d", &camp[i][0], &camp[i][1], &camp[i][2]);
            parent[i] = i;
        }
            
        int cnt = n;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int x = camp[i][0] - camp[j][0];
                int y = camp[i][1] - camp[j][1];
                int r = camp[i][2] + camp[j][2];
                int d = x*x + y*y;
 
                if (d <= r * r) {
                    if (find(i) != find(j)) {
                        merge(i, j);
                        cnt--;
                    }
                }
            }
        }
 
        printf("%d\n", cnt);
    }
    return 0;
}
cs


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

백준) 2206 벽 부수고 이동하기  (0) 2018.01.14
백준) 3055 탈출  (3) 2018.01.14
백준) 2606 바이러스  (0) 2017.10.09
백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28

2606. 바이러스

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





1. 접근


1번이 연결된 그래프의 노드수를 구하는 문제다.


인접리스트로 구성한 맵에 대해 1번 노드를 DFS / BFS 하면 되겟다.


DFS()로 풀어보자.



2. 풀이


DFS()는 재귀적으로 X에 연결된 노드가 몆개인지 알려다 줘야 한다.


DFS(1)이 DFS(2)를 불렀고, 최종적으로는 DFS(1)에게 DFS(2)에서 얼마나 진행되는지 알려줘야 하는 것이다.



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
#include <stdio.h>
#include <vector>
using namespace std;
 
int n, m, a, b;
int visit[101];
vector<vector<int>> map;
 
int dfs(int x) {
    int cnt = 1;
    visit[x] = 1;
 
    for (auto next : map[x]) {
        if (visit[next])
            continue;
 
        cnt += dfs(next);
    }
    return cnt;
}
 
int main() {
    scanf("%d %d", &n, &m);
    map.resize(n + 1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
 
    printf("%d", dfs(1) - 1);
 
    return 0;
}
cs


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

백준) 3055 탈출  (3) 2018.01.14
백준) 10216 Count Circle Groups  (0) 2017.10.09
백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28

2178. 미로 탐색

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




1. 접근


탐색은 BFS나 DFS로 조질 수 있다. 하지만 이동을 최소로 해야하기 때문에 BFS로 조져야 한다.



2. 풀이


이동의 횟수도 알아야 하기 때문에 큐질의 레벨을 기억해야 한다.


따라서 현재 레벨만큼 큐질을 하는 bfs질을 쓰자.



만약 (1, 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
#include <stdio.h>
#include <queue>
using namespace std;
 
struct col {
    int x, y;
};
 
char buf[101];
int map[100][100];
int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
int a, b;
 
int bfs() {
    queue<col> q;
    q.push({ 0, 0 });
 
    int cnt = 2;
 
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            int x = q.front().x;
            int y = q.front().y;
            q.pop();
 
            if (map[x][y] != 1)
                continue;
            map[x][y] = cnt;
 
            if (x == a - 1 && y == b - 1)
                return cnt;
 
            for (int j = 0; j < 4; ++j) {
                int xx = x + dir[j][0];
                int yy = y + dir[j][1];
 
                if (xx < 0 || xx >= a || yy < 0 || yy >= b)
                    continue;
                if (map[xx][yy] != 1)
                    continue;
 
                q.push({ xx,yy });
            }
        }
        cnt++;
    }
    return cnt;
}
 
int main() {
    scanf("%d %d", &a, &b);
    for (int i = 0; i < a; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < b; ++j)
            map[i][j] = buf[j] - '0';
    }
 
    printf("%d", bfs() - 1);
 
    return 0;
}
cs



bfs 도중에 재방문을 막는 visit 처리는 따로 visit[][] 배열을 쓰지 않아도, 기존 맵의 정보를 고쳐가면서도 할 수 있었다.

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

백준) 10216 Count Circle Groups  (0) 2017.10.09
백준) 2606 바이러스  (0) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28
백준) 9466 텀 프로젝트  (0) 2017.09.03

+ Recent posts

티스토리툴바