반응형

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

 

1944번: 복제 로봇

첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 미로를 입력받고, S와 K의 좌표에 번호를 붙입니다.

 

2. 2중 for문을 이용하여 S와 K의 모든 좌표들끼리 연결하고, edge 배열에 시작점과 도착점, 거리를 저장합니다.

 

3. edge 배열을 거리를 기준으로 오름차순으로 정렬합니다.

 

4. Union-Find를 이용하여 모든 노드를 연결하고, ans에 거리를 더합니다.

 

5. 위의 과정에서 노드를 연결할 때마다 cnt++ 해줍니다.

 

6. cnt == M일 경우 ans를 출력해 주고, 그렇지 않다면 -1을 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
struct node {
    int u;
    int v;
    int d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int N, M;
char arr[51][51];
int check[251][251];
int key[51][51];
vector<node> edge;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int vect[251];
 
void getEdge(int y, int x)
{
    int u = key[y][x];
    int visited[50][50] = { 0 };
    queue<node> q;
    q.push({ y,x,0 });
    visited[y][x] = 1;
 
    while (!q.empty()) {
        const int y = q.front().u;
        const int x = q.front().v;
        const int cnt = q.front().d;
        q.pop();
 
        if ((arr[y][x] == 'S' || arr[y][x] == 'K') && cnt != 0) {
            int v = key[y][x];
            if (check[u][v] != 1 && check[v][u] != 1) {
                edge.push_back({ u,v,cnt });
                check[u][v] = 1;
                check[v][u] = 1;
            }
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy > 0 && yy < N - 1 && xx>0 && xx < N - 1) {
                if (arr[yy][xx] != '1' && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
}
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 1; i <= M; i++) {
        vect[i] = i;
    }
 
    int cnt = 1;
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (arr[i][j] == 'S') {
                key[i][j] = 0;
            }
            else if(arr[i][j] == 'K'){
                key[i][j] = cnt++;
            }
        }
    }
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (arr[i][j] == 'S' || arr[i][j] == 'K') {
                getEdge(i, j);
            }
        }
    }
 
    sort(edge.begin(), edge.end(), cmp);
 
    int ans = 0;
    cnt = 0;
 
    for (auto& next : edge) {
        const int u = next.u;
        const int v = next.v;
        const int d = next.d;
 
        if (Find(u) != Find(v)) {
            Union(u, v);
            ans += d;
            cnt++;
        }
    }
 
    if (cnt == M) {
        printf("%d", ans);
        return 0;
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19
[ 백준 ] 20010번 - 악덕 영주 혜유 (C++)  (0) 2023.02.18
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
[ 백준 ] 7570번 - 줄 세우기 (C++)  (0) 2023.02.14

+ Recent posts

티스토리툴바