문제 설명에서 가장 먼거리에 숨은 헛간의 번호를 찾는다고 하였으나 사실상 시작점으로 부터
각 헛간까지 우회하는 경로가 없어야하므로, 다익스트라로 각 헛간까지의 최단거리를 
갱신해주면된다. 

중요한것은 거리를 기준으로 정렬하였을때, 초기 입력받은 번호에 대한 정보를 잃지 않기 위해서 

구조체 형식으로 거리배열을 생성하고, 갱신하였다. 

나머지는 무방향 그래프이면서 최대거리와 최대거리 요소의 갯수만 찾아주면 간단히 해결된다.



<code>

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
//pda_pro12
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
 
#define all(x) x.begin(), x.end()
#define INT 0x7fffffff
#define N_ 20001
 
using namespace std;
 
struct DATA { int num, value; };
 
vector<pair<int, int>> v[N_]; priority_queue<pair<int, int>> pq;
int n, m; DATA dst[N_]; int x, y; vector<int> ans;
 
bool cmp(DATA u, DATA t) {
    return u.value < t.value;
}
bool cmp1(DATA u, DATA t) {
    return u.num < t.num;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    while (m--) {
        cin >> x >> y;
        v[x].push_back({ y, 1 });
        v[y].push_back({ x, 1 });
    }
    for (int i = 1; i <= n; i++) {
        dst[i].value = INT, dst[i].num = i;
    }
    dst[1].value = 0;
    pq.push({ 1, 0 });
    while (!pq.empty()) {
        int v_x = pq.top().first;
        int dis = -pq.top().second;
        pq.pop();
        if (dis > dst[v_x].value) continue;
        for (int i = 0; i < v[v_x].size(); i++) {
            int next = v[v_x][i].first;
            int n_dis = dis + v[v_x][i].second;
            if (n_dis < dst[next].value) {
                dst[next].value = n_dis;
                pq.push({ next, -n_dis });
            }
        }
    }
    sort(dst + 1, dst + 1 + n, cmp);
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        if (Max < dst[i].value) {
            Max = dst[i].value;
            ans.clear();
            ans.push_back(dst[i].num);
        }
        else if (Max == dst[i].value)
            ans.push_back(dst[i].num);
    }
    sort(all(ans));
    cout << ans.front() << ' ' << Max << ' ' << ans.size();
 
    return 0;
}


저작자표시

'PS) BOJ > Dijkstra' 카테고리의 다른 글

[C++]알고스팟[백준1261]  (0) 2018.08.15





처음엔 A....뭐야... 그냥 bfs로 슥삭하면되겠네....

라고 생각했지만 아니었다. 

더 많은 칸을 가야하지만 최소의 벽을 깨고 가는 경우가 있기 때문이었다. 

기냥 2차원 거리 배열을 선언해서 INF로 초기화해주자. 

어차피 시작점은 0,0 이니 거리배열 [0][0] = 0으로 해주자 

똑같이 Priority_Queue를 사용하는데 인자로 <int,int> int를 주었다. 

Vertext 하나의 위치정보가 x,y좌표이므로 ~
간선정보는 배열자체에 주어져있으므로 필요없고, 연결 노드야 현시점에서 4방향

탐색을 통한 지점일테고....

다만 시간줄이려고 cin.tie(NULL)해놓고 scanf를 써서 맞왜틀을 30분 겪었다...ㅎㅎ

나머지는 단순한 다익스트라로 쉽게 풀린답


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



<CODE>


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
// pda_pro12
#include<algorithm>
#include<queue>
#include<iostream>
 
#define lng(x) x.length()
#define sz(x) x.size()
#define N_ 101
#define INT 0x7fffffff
using namespace std;
 
int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,-1,1 };
int n, m, a[N_][N_], dst[N_][N_];
priority_queue<pair<pair<int, int>, int>> pq; 
 
int main() {
    cin >> n >> m; 
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%1d", &a[i][j]),dst[i][j] = INT; 
    dst[0][0] = 0;
    pq.push({ {0,0},0 }); 
    while (!pq.empty()) {
        int v_x = pq.top().first.first; int v_y = pq.top().first.second; 
        int dis = -pq.top().second;
        pq.pop(); 
        if (dis > dst[v_x][v_y]) continue; 
        for (int i = 0; i < 4; i++) {
            int nx_x = v_x + dx[i]; int ny_y = v_y + dy[i]; 
            if (nx_x < 0 || nx_x >= m || ny_y < 0 || ny_y >= n) continue; 
            int n_dis = dis + a[nx_x][ny_y]; 
            if (n_dis < dst[nx_x][ny_y]) {
                dst[nx_x][ny_y] = n_dis; 
                pq.push({ {nx_x, ny_y}, -n_dis }); 
            }
        }
    }
    cout << dst[m - 1][n - 1]; 
    return 0;
}


저작자표시

'PS) BOJ > Dijkstra' 카테고리의 다른 글

[C++]숨바꼭질[백준 6118]  (0) 2018.08.15

+ Recent posts

티스토리툴바