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


가장 쉬운 bfs문제입니다.

최소의 칸 수를 구하라? 즉 bfs를 이용해서 가장 먼저 도달하는 너비를 출력하라는 말입니다.

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
#include <stdio.h>
 
const int QUEUE_SIZE = 100 * 100 * 4;
 
typedef struct qs {
    int x, y, b;
}qs;
 
 
typedef struct queue {
    qs data[QUEUE_SIZE];
    int front, rear;
 
    queue() {
        front = rear = 0;
    }
 
    int empty() {
        return front == rear;
    }
 
    void push(qs d) {
        rear = (rear + 1) % QUEUE_SIZE;
        data[rear] = d;
    }
 
    qs pop() {
        front = (front + 1) % QUEUE_SIZE;
        return data[front];
    }
}queue;
 
 
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
char map[100][100];
int visit[100][100];
 
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
 
    getchar();
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    queue q;
    q.push(qs{0, 0, 1});
    visit[0][0] = 1;
    
    while (!q.empty()) {
        qs front = q.pop();
 
        if (front.x == m - 1 && front.y == n - 1) {
            printf("%d", front.b);
            break;
        }
 
        for (int i = 0; i < 4; i++) {
            int nx = front.x + dx[i];
            int ny = front.y + dy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
            if (map[nx][ny] == '0') continue;
 
            visit[nx][ny] = 1;
            q.push(qs{ nx, ny, front.b + 1 });
        }
 
    }
 
    return 0;
}
cs


저작자표시

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

[2667] 단지번호붙이기  (0) 2017.09.15
[10216] Count Circle Groups  (0) 2017.08.10
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

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


문제 이해를 잘못해서.. 해결하는데 엄청난 시간이 걸렸습니다.


이 문제는 (0, 0)에서 입력 받은 K이하의 노드를 거쳐서  (10000, 10000)으로 이동할 때 드는 연료의 최대값의 최솟값을 구하는 문제입니다.


(0, 0)을 A라고 가정하고 (10000, 10000)을 D라고 가정했을 때, A - B(임의의 노드)로 가는 연료가 1000이고 B - C(임의의 노드)로 가는 연료가 100이라면


A - B구간에서 1000만큼 필요했으므로 답은 1000이 나와야합니다.


이것을 모든 노드에 대해서 실행해보면 됩니다.


이분탐색을 이용해서 해당 비용만을 이용해서 (0, 0)에서 (10000, 10000) 목적지로 이동할 수 있는지를 계속해서 실행하면 됩니다.(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
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
vii pos;
bool visit[(int)1e3 + 2];
 
int d(pii a, pii b) {
    int x = b.first - a.first;
    int y = b.second - a.second;
 
    return (int)ceil(sqrt(x * x + y * y) / 10);
}
 
bool bfs(int max_cost, int n, int k) {
    memset(visit, 0, sizeof(visit));
 
    queue<pii> q;
    q.push(mp(0, 0)); // from, k
 
    while (!q.empty()) {
        int from = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (from == pos.size() - 1) {
            if (cnt <= k + 1) return 1;
            else return 0;
        }
 
        for (int i = 1; i < pos.size(); i++) {
            if (visit[i]) continue;
 
            if (d(pos[i], pos[from]) <= max_cost) {
                visit[i] = 1;
                q.push(mp(i, cnt + 1));
            }
        }
    }
    
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, k;
    cin >> n >> k;
 
    pos.push_back(mp(0, 0));
 
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
 
        pos.push_back(mp(a, b));
    }
 
    pos.push_back(mp(1e4, 1e4));
 
    int left = 1, right = d(mp(0, 0), mp(1e4, 1e4));
 
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (bfs(mid, n, k)) right = mid - 1;
        else left = mid + 1;
    }
 
    cout << left;
 
    return 0;
}
cs


저작자표시

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

[12842] 튀김 소보루  (0) 2017.08.23
[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19

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


(친구)와 (친구의 친구)의 최대치를 출력하는 문제입니다.

간단하게 생각했고 bfs를 이용하여 너비 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 <iostream>
#include <string.h>
#include <queue>
 
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE 500000
//ios::sync_with_stdio(false); cin.tie(0);
 
char map[55][55];
bool visit[55];
int n;
 
int bfs(int vertex) {
    memset(visit, 0, sizeof(visit));
 
    queue<pair<int, int> > q;
    
    q.push(make_pair(vertex, 0));
    visit[vertex] = 1;
 
    while (!q.empty()) {
        int now = q.front().first;
        int breath = q.front().second;
        q.pop();
 
        if (breath == 2) break; //친구의 친구가 되면 탈출
 
        for (int i = 0; i < n; i++) {
            if (map[now][i] == 'Y' && !visit[i]) {
                visit[i] = 1;
                q.push(make_pair(i, breath + 1));
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) ret += visit[i];
 
    return ret - 1; // 자기 자신은 제외
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    //인풋
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) ret = max(ret, bfs(i));
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

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

[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23
[14503] 로봇 청소기  (2) 2017.04.18

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


흠흠...

사실 최단 거리라기 보다는.. 가장 비용을 적게 들여서(가장 벙커를 적게 방문하면서) 목적지로 도달하는 문제입니다.


처음에 접근은 이분탐색으로 했습니다.

벙커들을 sort하여 갈 수 있는 시간내로 이동할 수 있는 최대 거리로 이동을 하여서 목적지에 도달하게 했습니다.


이 문제에서 이분탐색을 쓰면 생기는 오류는 방향입니다.

x, y 좌표가 있기 때문에 방향이 있어서 최대한의 거리가 절대값이기 때문에 오류가 발생합니다.


그래서 dfs로 해결하려 했으나 dfs는 최적의 해를 보장해주지 않기 때문에 완전 탐색을 해야만합니다.

시간초과로 실패했습니다.


해결 방법은 bfs 혹은 다익스트라로 해결하시면 됩니다.

사실 해보니깐.. 다익스트라는 딱히 필요없는듯.. 어차피 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
#include <cstdio>
#include <queue>
 
using namespace std;
 
#define mp make_pair
#define ll long long
 
vector<pair<double, double> > b;
bool visit[1005];
int v, m;
double xs, ys;
double xt, yt;
 
double distance(pair<double, double> a, pair<double, double> b) {
    double x = a.first - b.first;
    double y = a.second - b.second;
    return x*x + y*y;
}
 
int main() {
    scanf("%d %d", &v, &m);
    scanf("%lf %lf", &xs, &ys);
    scanf("%lf %lf", &xt, &yt);
 
    double ttx, tty;
    while (~scanf("%lf%lf", &ttx, &tty)) {
        b.push_back(mp(ttx, tty));
    }
    b.push_back(mp(xt, yt)); //도착점 삽입
 
    queue<pair<int, pair<double, double> > > q;
    q.push(mp(0, mp(xs, ys)));
    
    ll md = v * m * 60; // 이동할 수 있는 최대거리
    md *= md; // 최대거리의 제곱
 
    while (!q.empty()) {
        int cnt = -q.front().first;
        double x = q.front().second.first;
        double y = q.front().second.second;
        q.pop();
 
        if (x == xt && y == yt) {
            printf("Yes, visiting %d other holes.\n", cnt - 1);
            return 0;
        }
 
        for (int i = 0; i < b.size(); i++) {
            if (visit[i] || distance(mp(x, y), b[i]) > md) continue;
            visit[i] = 1;
            q.push(mp(-(cnt + 1), b[i]));
        }
    }
 
    puts("No.");
 
    return 0;
}
cs


저작자표시

'알고리즘 > 최단 거리' 카테고리의 다른 글

[14588] Line Friends(small)  (0) 2017.07.23
[1507] 궁금한 민호  (0) 2017.07.08

+ Recent posts

티스토리툴바