백준의 다리만들기2(17472) 문제이다.

[ 문제 바로가기 ]


[ 문제풀이 ]

1) 이번 글에서는 지난 글(다리만들기2 정답도출을 완전탐색으로 도출)에서 했던 방식과는 달리

   MST(Minimum Spanning Tree)로 구하는 법을 알아보자.

   사실, 지난 글과 코드의 대부분이 비슷하다. 정말 마지막 부분만 약간 다르기 때문에

   이 글에서는 마지막 부분에 대해서만 설명을 할 것이다.

   지난 번 글을 참고하고 싶다면 아래의 글을 읽으면 된다.

   [ 백준(17472 ) - (1) ]


2) 정말 다 똑같은데, 마지막 부분에서 크루스칼 알고리즘을 이용해서 최소 스패닝 트리를 구하는 것으로 구현을 하였다.

   아직 크루스칼 알고리즘을 잘 모른다면 아래의 글을 읽고 오자.

   [ 크루스칼 알고리즘 알아보기 ]


   정말 더 이상 설명할 말이 없다...

   본인이 크루스칼 알고리즘으로 MST를 구현해서 문제를 풀 때 실수했던 부분은

   "모든 섬들이 연결되는가" 부분을 체크해주지 않아서 fail을 여러번 받았다.

   크루스칼 알고리즘 같은 경우, 하나의 섬이 연결이 되지 않더라도 따로 처리를 해주지 않으면 정답을 도출해 버리는

   경우가 있었다.

  

   위와 같은 맵이 존재할 때, 빨강색 동그라미 친 섬은 그 어떤 섬과도 연결될 수가 없다.

   따라서, 위의 케이스의 정답은 -1이 맞다. 하지만 크루스칼에서 따로 처리를 해주지 않았더니 나머지 3개의 섬들간의

   최소거리만 구하는 경우가 있어서 이 부분을 처리해 주었다.

   처음에 처리하는 방식은, "1"번섬의 부모노드를 기준으로, 부모노드가 다른 어느 한 섬이라도 있으면 연결이 되지 않았다

   고 표시를 해 주었는데 단순히 이러한 방식으로는 해결되지 못하는 부분이 있다.

   본인은 먼저 합치는 경우(Union)에 무조건 더 작은 부모노드 번호를 따라 가도록 만들어 주었다.

   예를 들어서 1번 노드의 부모노드가 1번, 2번 노드의 부모노드가 2번일 때, 2번노드의 부모노드가 더 작은 번호인

   1번 노드로 바뀌도록 설정해 주었다. 이렇게 구현한다면 모든 섬들이 다 연결되었을 경우, 모든 섬들의 부모노드 번호가

   1번이 되어 있을 것이다. 하지만, 1번 노드와 직접적으로 연결이 되지 않는 섬들 때문에 이러지 않은 경우가 존재한다.

   아래의 예시를 한번 봐보도록 하자.

  

    위의 경우를 크루스칼 알고리즘에서 부모노드를 통일 시키는 과정을 생각해보자. 먼저 거리가 짧은 순으로 정렬을
    하게되면 다음과 같게 될 것이다.
    2번섬과 4번섬의 거리 = 2
    3번섬과 5번섬의 거리 = 2
    4번 섬과 5번 섬의 거리 = 2
    4번 섬과 6번 섬의 거리 = 2
    2번 섬과 3번 섬의 거리 = 3
    1번 섬과 5번 섬의 거리 = 4
    이 순서대로 Union 과정을 진행하게 될 것이다. (무조건 작은 섬의 번호가 부모노드가 되도록 진행)
    이 때, 1번부터 6번 섬까지 부모노드 번호를 순서대로 적어보면 아래와 같이 될 것이다.
    { 1, 2, 2, 2, 1, 2 }
    즉, 모든 섬이 연결될 수 있음에도 '1'번으로 통일이 되지 않았다. 왜냐하면, 1번 섬과 직접적으로 연결이 되어
    있지 않은 섬이 존재하거나, 존재하더라도 그 거리가 다른 섬들간의 거리에 비해서 상대적으로 더 길 경우
    Union과정이 더 늦게 진행되기 때문이다.
    만약에, 1번섬과 5번 섬의 거리가 '4'가 아닌, '2'였다면 결과가 달라졌을 것이다.
    그래서 본인은 Union 과정을 총 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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 10
#define ISLAND_MAX 6 + 1
#define INF 1000
using namespace std;
 
int N, M, Area_Num, Answer;
int MAP[MAX][MAX];
int Label[MAX][MAX];
int Dist[ISLAND_MAX][ISLAND_MAX];
int Parent[ISLAND_MAX];
 
bool Visit[MAX][MAX];
 
vector<pair<int, int>> V;
vector<pair<int, int>> Area_Pos[MAX + 1];
vector<pair<int, pair<int, int>>> Node;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    for (int i = 0; i < ISLAND_MAX; i++)
    {
        for (int j = 0; j < ISLAND_MAX; j++)
        {
            Dist[i][j] = INF;
        }
    }
 
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 1) V.push_back(make_pair(i, j));
        }
    }
}
 
void BFS(int a, int b, int Num)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
    Label[a][b] = Num;
    Area_Pos[Num].push_back(make_pair(a, b));
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (Visit[nx][ny] == false && MAP[nx][ny] == 1)
                {
                    Visit[nx][ny] = true;
                    Label[nx][ny] = Num;
                    Q.push(make_pair(nx, ny));
                    Area_Pos[Num].push_back(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void MakeLabel()
{
    int LabelNum = 1;
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
 
        if (Visit[x][y] == false) BFS(x, y, LabelNum++);
    }
    Area_Num = LabelNum;
}
 
void DFS(int x, int y, int dir, int B_Size, int Start, int End)
{
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (nx < 0 || ny < 0 || nx >= N || ny >= M) return;
 
    if (MAP[nx][ny] == 0) DFS(nx, ny, dir, B_Size + 1, Start, End);
    else if (MAP[nx][ny] == 1)
    {
        if (Label[nx][ny] == End)
        {
            if (B_Size > 1)
            {
                if (Dist[Start][End] > B_Size)
                {
                    Dist[Start][End] = B_Size;
                    Dist[End][Start] = B_Size;
                }
                return;
            }
        }
        else return;
    }
}
 
int Reverse(int dir)
{
    if (dir == 0) return 1;
    else if (dir == 1) return 0;
    else if (dir == 2) return 3;
    else if (dir == 3) return 2;
}
 
void MakeBridge(int Start, int End)
{
    for (int i = 0; i < Area_Pos[Start].size(); i++)
    {
        int x = Area_Pos[Start][i].first;
        int y = Area_Pos[Start][i].second;
 
        for (int j = 0; j < 4; j++)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == 0)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        if (k == Reverse(j)) continue;
                        DFS(x, y, k, 0, Start, End);
                    }
                }
            }
        }
    }
}
 
int Find(int x)
{
    if (Parent[x] == x) return x;
    else return Find(Parent[x]);
}
 
void Union(int x, int y)
{
    int px = Find(x);
    int py = Find(y);
 
    if (px != py)
    {
        if (px < py) Parent[y] = px;
        else Parent[x] = py;
    }
}
 
bool SameParent(int x, int y)
{
    x = Find(x);
    y = Find(y);
 
    if (x != y) return false;
    return true;
}
 
void FindDistance()
{
    for (int i = 1; i < Area_Num; i++)
    {
        for (int j = i + 1; j < Area_Num; j++)
        {
            MakeBridge(i, j);
            if (Dist[i][j] == INF) continue;
            Node.push_back(make_pair(Dist[i][j], make_pair(i, j)));
        }
    }
 
    sort(Node.begin(), Node.end());
    for (int i = 1; i < Area_Num; i++) Parent[i] = i;
    for (int NCheck = 1; NCheck <= 2; NCheck++)
    {
        for (int i = 0; i < Node.size(); i++)
        {
            int Node1 = Node[i].second.first;
            int Node2 = Node[i].second.second;
            
            if (SameParent(Node1, Node2) == false)
            {
                Union(Node1, Node2);
                if(NCheck == 1)    Answer = Answer + Node[i].first;
            }
        }
    }
}
 
bool Check()
{
    int x = Parent[1];
    for (int i = 2; i < Area_Num; i++)
    {
        int y = Find(i);
        if (y != x) return false;
    }
    return true;
}
 
void Solution()
{
    MakeLabel();
    FindDistance();
 
    if (Answer == 0) cout << -1 << endl;
    else
    {
        if (Check() == true) cout << Answer << endl;
        else cout << -1 << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}
 
cs
cs


저작자표시

'[ BOJ Code ] > # BOJ -' 카테고리의 다른 글

[ 백준 17780 ] 새로운 게임 (C++)  (9) 2019.10.28
[ 백준 17779 ] 게리멘더링2 (C++)  (0) 2019.10.23
[ 백준 17472 ] 다리만들기2 (C++) (1)  (16) 2019.09.24
[ 백준 17471 ] 게리멘더링 (C++)  (6) 2019.09.21
[ 백준 7453 ] 합이 0인 네 정수 (C++)  (14) 2019.09.17

+ Recent posts

티스토리툴바