문제를 살펴보면 딱히 어려운 문제는 아니다. 

그냥 다익스트라 2차원으로 돌리면된다. 

흰색이 1 검은색이 0이라는 점에 착안하면 검은색에 가중치를 두기 위해 필자는 원본을 toggle 해줬다. 

그냥 벡터도 필요없이 dst 2차원을 갱신해주며 다익스트라를 돌려주자
(요즘 너무 쉬운것만 올리는것 같다 - 맨날 이소리하고 맨날 쉬운거 올린다)

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

2665번: 미로만들기
2665번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 미로만들기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 2961 1257 858 42.644% 문제 n×n 바둑판 모양으로 총 n 2 개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어가 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으
www.acmicpc.net

<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
// pda_pro12
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
 
#define INT 0x7fffffff
#define N_ 51
 
using namespace std;
 
int n, a[N_][N_], dst[N_][N_], dx[] = { -1,1,0,0 }, dy[] = { 0,0,1,-1 };
priority_queue<pair<pair<int, int>, int>> pq;
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            scanf("%1d", &a[i][j]);
            a[i][j] = (a[i][j] == 0) ? 1 : 0; 
            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 = v_x + dx[i]; int ny = v_y + dy[i]; 
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 
            int n_dis = dis + a[nx][ny]; 
            if (n_dis < dst[nx][ny]) {
                dst[nx][ny] = n_dis; 
                pq.push({ {nx, ny}, -n_dis });
            }
        }
    }
    cout << dst[n - 1][n - 1]; 
    return 0;
}


저작자표시

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

[C++] 네트워크 연결 [백준 3780]  (0) 2018.08.17
[C++] 공항 [BOJ 10775]  (0) 2018.08.17

Disjoint_Set의 개념으로 길이 배열을 한가지 더 선언해주어서 절대 차이만큼만 

더해주면서 저장하면 되는 것이었다. 

find 와 init 과정에서 parent 배열과 길이를 저장할 배열을 따로 만들어주었다. 

find를 호출할때마다 해당 노드의 루트노드를 탐색하고 루트노드까지의 길이를 해당 인덱스의

길이 배열에 저장해주었다. 

(어렵게 생각하기보단 풀리지 않는다면 Disjoint_set의 과정을 완벽히 이해해보시길 바랍니다.)

그래도 이해가 가지않는다면 댓글과 쪽지를 주세요!

스티커 이미지

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

3780번: 네트워크 연결
문제 종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다. 어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다. 클러스터 B를 제공하는 기업 J를 고른다.
www.acmicpc.net

<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
//pda_pro12
#include<iostream>
#include<algorithm>
 
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define N_ 20001
#define mod (int)1e3
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pll;
typedef double db;
 
int n, m, t, par[N_], len[N_];
 
void init() {
    for (int i = 1; i <= n; i++)
        par[i] = i, len[i] = 0;
    return;
}
 
int find(int x) {
    if (x == par[x])
        return x;
    else {
        int tmp = find(par[x]); 
        len[x] += len[par[x]]; 
        par[x] = tmp; 
        return tmp;
    }
}
 
void Merge(int x, int y) {
    len[x] = abs(x - y) % mod; 
    par[x] = y; 
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    while (t--) {
        cin >> n;
        init(); 
        char inp; int a, b;
        while (1) {
            cin >> inp;
            if (inp == 'O')
                break; 
            else if (inp == 'E') {
                cin >> a;
                find(a); 
                cout << len[a] << '\n';
            }
            else if (inp == 'I') {
                cin >> a >> b;
                Merge(a, b);
            }
        }
    }
    return 0;
}


저작자표시

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

[C++]미로 만들기 [BOJ 2665]  (0) 2018.08.21
[C++] 공항 [BOJ 10775]  (0) 2018.08.17


굉장히 간단한 문제를 조건하나를 빠트려서 계속 헛다리 짚은 문제이다...
( 내시간... )

n번 게이트에 도킹 되면 가장 인접하면서 낮은 번호의 게이트로 도킹이 되고, 연결해야할 게이트가 
0번 밖에 남지 않았다고 한다면 마쳐주면된다. 

도킹 게이트가 0임을 포착한 순간 바로 입력하던 반복문도 빠져나오고 현 게이트 수를 출력하고 종료시켜줘야한다. 
(이거때매 30분넘게 해맸다...)

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

<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<iostream>
#define N_ 100001
 
using namespace std;
 
int g, p, par[N_], inp, cnt;
 
void init() {
    for (int i = 1; i <= g; i++)
        par[i] = i;
    return;
}
 
int find(int x) {
    if (x == par[x])
        return x;
    return par[x] = find(par[x]);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> g >> p;
    init();
    for (int i = 1; i <= p; i++) {
        cin >> inp;
        if (find(inp) == 0) {
            break;
        }
        if (find(inp)) {  // 내가 도킹하려는 곳이 가능한지 확인 
            cnt++;
            par[find(inp)] = find(find(inp) - 1);
        }
    }
    cout << cnt << '\n';
    return 0;
}


저작자표시

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

[C++]미로 만들기 [BOJ 2665]  (0) 2018.08.21
[C++] 네트워크 연결 [백준 3780]  (0) 2018.08.17

+ Recent posts

티스토리툴바