처음엔 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








입국심사대 N이 10만,   입국 처리인원이 10억으로 Max값이 주어진다. 각 심사대에서 처리하는데 소요되는 시간 또한 10억이다. 완탐으로 1초안에 해결이 불가능한 문제이다. 
이걸 완탐돌린다면... 생각만 해도 끔찍하다. 

착안해낸 아이디어
1. 하한값을 1로 잡고 상한값을 10억*10만값으로 가정하고 풀이하였다.
    (WorstCase: 각 심사대10억*10만)

2.  이분탐색으로 시간을 가정하고 해당 시간으로 10만의 심사대에서 처리하고자하는 인원 M을 처리할
     수 있는지 혹은 처리하기에 시간이 부족한지를 살펴본다. 

3. 처리시간이 부족하다면 하한을 중간값+1로 설정하여 중간값을 다시 설정하고 이분탐색을 진행한다. 
    인원처리가 가능하다면 상한값을 중간값-1로 설정하여 left값이 right를 초과하는 순간 종료된다. 

4. lft는 항상 최소한의 가능한순간까지의 하한값을 증가시킬것이다. right값을 lft값이 초과하는 순간
   빠져나와버리므로 수용가능한 경우의 최소 mid값과 lft값은 일치한다. 
시간 복잡도 :  O(NlogN) 
탐색과정을 보면 다음과 같다 





<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
// pda_pro12
#include<iostream>
#include<algorithm>
#define N_ 100000
#define Upper 100000000000000   // N_ * M(max)
 
using namespace std;
 
typedef long long ll;
ll lft, rgt, n, m;   int a[N_];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        cin >> a[i];
 
    ll lft = 1;  ll rgt = Upper;   // Lower ,  Upper
 
    while (lft <= rgt) {
        
        ll mid = (lft + rgt) >> 1;
        ll Sum = 0;
        for (int i = 0; i < n; i++)
            Sum += (mid / a[i]);
        if (Sum >= m)
            rgt = mid - 1; 
        else
            lft = mid+1;
    }
    cout << lft << '\n';
    return 0;
}


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

[C++]수열 걷기[백준 4929]  (0) 2018.08.21
[C++] 랜선 자르기 [BOJ 1654]  (0) 2018.08.16
[C++] K번째 수[백준 1300]  (0) 2018.08.16
[C++] 게임 [백준 1072]  (0) 2018.08.16

개인적으로 '감시' 문제보다 구현할게 많지 않아서 간단하게 풀수 있는 문제입니다.  

먼저 '연구소'라는 문제를 풀어본사람은 비슷하다는 느낌을 많이 받았을 것입니다.  

먼저 사다리의 시작점-도착점이 일치하는지 여부를 판별하기전에 사다리부터 놓아야합니다.  

문제 해결 절차 

1. 사다리를 h*n인덱스를 탐색하며 양사이드 [h][n-1]과 [h][n+1], [h][n]이 비어있는 사다리인지 확인 
   해본다. (h가 세로선이므로 행 n이 가로선 번호이므로 열이다.헷갈리지 않게 주의하자) 
2. 비어있다면 사다리를 놓고 재귀호출~ 그리고 재귀호출 끝나고 돌아오면 백트래킹으로 다시 사다리를 
    없애주도록 하자. 생각보다 복잡도가 심하지 않은 편이다. (양사이드와 현재 인덱스가 있으므로 )
 시간을 최대한 줄이자
- 가지치기를 잘하여 사다리들이 시작점으로 모두 도착하는경우 더이상 탐색하지 않는다. 
- 탐색과정에서 행단위로 양사이드 및 해당 열에 사다리를 모두 놓았다면, 해당 행 이상인 부분만 탐색. 

위 조건만 잘 만족시켜준다면 시간안에는 통과할수 있을 것이다. 




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

<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
// Minerba
#include<iostream>
using namespace std;
bool a[31][11]; int n, m, h, Ladder;    bool res;
bool Count_Ladder() {
    for (int i = 1; i <= n; i++) { // 세로선 번호  // i는 반복문 시작전 최초의 시작점, pt는 변경될 시작점
        int pt = i;
        for (int j = 1; j <= h; j++) {
            if (a[j][pt]) pt += 1;   // 오른쪽으로 이동
            else if (pt - 1 > 0 && a[j][pt - 1]) pt -= 1; // 왼쪽으로 이동 
        }
        if (i == pt) continue;
        else
            return false;
    }
    res = true; 
    return true;
}
 
void dfs(int x, int cnt) {
    if (res) return;
    if (cnt == Ladder) {
        if (Count_Ladder())  m = cnt;
        return;
    }
    for (int i = x; i <= h; i++) {   // 기존 행에 사다리를 놓았다면 해당 행과 같거나 더 커야한다.
                                     // 사다리가 역주행해서 위로 올라갈순 없으니...
        for (int j = 1; j < n; j++) {
            if (!a[i][j]) {
                if (!a[i][j - 1] && !a[i][j + 1]) { // 연속되지 않은 가로선 
                    a[i][j] = 1;
                    dfs(i, cnt + 1);
                    a[i][j] = 0;
                }
            }
        }
    }
    return;
}
 
int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> h;
    while (m--) {
        int x, y; cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 0; i <= 3; i++) {
        Ladder = i;
        dfs(1, 0);
        if (res) break;
    }
    if (!res) cout << -1 << '\n';
    else cout << m << '\n';
    return 0;
}














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

[C++]감시[백준 15683]  (0) 2018.08.15

+ Recent posts

티스토리툴바