Post

(백준) 24338번 - 가희와 베개

(백준) 24338번 - 가희와 베개

Posted
By whqtker
16 min read
(백준) 24338번 - 가희와 베개

문제

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

풀이

이해를 위한 설명

문제를 정리하면 다음과 같다. 편의 상 고도 1은 고지대, 고도 0은 저지대라고 표현한다.

  1. 격자판에는 1, ., B, P, #, ?가 존재한다. 1은 고지대, ., B, P는 저지대이다.
  2. ?에 적절한 경사로를 설치하여 고지대와 저지대를 연결할 수 있다.
  3. 시작 좌표로부터 B 또는 P에 도달 가능하도록 경사로를 설치하거나, 불가능한 경우 `-1 를 출력한다.

전체적인 흐름은 다음과 같다.

  1. BFS를 돌며 인접한 고지대/저지대를 그룹핑한다.
  2. ?에 적절한 경사로를 설치하며, 출발지와 도착지가 연결 가능하다면 그러한 격자판을, 그렇지 않으면 -1을 출력한다.

위 내용으로는 단순한 BFS/DFS, 더 나아간다면 분리 집합까지 생각할 수 있으나, 추가로 고수준의 최적화와 다양한 엣지 케이스를 고려해야 하는 문제이다.

코드

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

#include <iostream>
#include <vector>
#include <queue>

#define SIZE 739

using namespace std;

struct Change {
    int node, p, r; // 노드 번호, parent, rank
    bool ht; // hasTar
};

struct Cand {
    char dir;
    int a, b; // 두 영역 번호
};

int n, m, sx, sy;
char board[SIZE][SIZE];
int region[SIZE][SIZE];
vector<pair<int, int>> pos; // ? 좌표
vector<pair<int, int>> tar; // B, P 좌표
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
char dir[4] = { 'N','E','S','W' };
int parent[SIZE * SIZE]; // 영역 번호, 부모
int rnk[SIZE * SIZE];
int isHigh[SIZE * SIZE];
bool hasTar[SIZE * SIZE];
vector<Change> history;
vector<Cand> cands[18];
int startRegion;

int Find(int x) {
    while (parent[x] != x) x = parent[x];

    return x;
}

// 실제로 합쳐졌다면 true
bool Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);

    if (px == py) {
        history.push_back({ px,parent[px],rnk[px],hasTar[px] });
        history.push_back({ py,parent[py],rnk[py],hasTar[py] });
        return false;
    }
    if (rnk[px] < rnk[py]) swap(px, py);
    history.push_back({ px,parent[px],rnk[px],hasTar[px] });
    history.push_back({ py,parent[py],rnk[py],hasTar[py] });
    parent[py] = px;
    hasTar[px] = hasTar[px] || hasTar[py];
    if (rnk[px] == rnk[py]) rnk[px]++;
    return true;
}

void rollback() {
    Change cy = history.back();
    history.pop_back();
    Change cx = history.back();
    history.pop_back();

    parent[cx.node] = cx.p;
    rnk[cx.node] = cx.r;
    hasTar[cx.node] = cx.ht;
    parent[cy.node] = cy.p;
    rnk[cy.node] = cy.r;
    hasTar[cy.node] = cy.ht;
}

bool connected() {
    return hasTar[Find(startRegion)];
}

void printBoard() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == '?') cout << 'N';
            else cout << board[i][j];
        }
        cout << "\n";
    }
}

// ?에 대해 유효한 경사로를 설치한다.
void dfs(int cnt) {
    if (cnt == pos.size()) {
        if (connected()) {
            printBoard();
            exit(0);
        }

        return;
    }

    if (cands[cnt].empty()) {
        dfs(cnt + 1);

        return;
    }

    int x = pos[cnt].first;
    int y = pos[cnt].second;

    for (auto e : cands[cnt]) {
        board[x][y] = e.dir;
        bool merged = Union(e.a, e.b);
        if (merged && connected()) {
            printBoard();
            exit(0);
        }

        dfs(cnt + 1);
        rollback();
        board[x][y] = '?';
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    // 먼저 모든 좌표에 대해 BFS를 돌며 독립된 영역을 넘버링한다.
    // 이후 ?에 대해 가능한 조합들을 생성한다.
    // 이후 모든 ?에 대해 조건을 만족하면 Union한다.
    // B, P가 속한 영역과 시작 좌표의 parent가 같은 영역에 있다면 답을 출력한다.

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            if (board[i][j] == '?') pos.push_back({ i,j });
            else if (board[i][j] == 'B' || board[i][j] == 'P') tar.push_back({ i,j });
        }
    }

    int regionCounter = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == '#' || board[i][j] == '?') continue;
            if (region[i][j] != 0) continue;

            int counter = ++regionCounter;
            region[i][j] = counter;
            isHigh[counter] = (board[i][j] == '1');
            queue<pair<int, int>> q;
            q.push({ i,j });

            while (!q.empty()) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();

                for (int idx = 0; idx < 4; idx++) {
                    int nx = x + dx[idx];
                    int ny = y + dy[idx];

                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (board[nx][ny] == '?' || board[nx][ny] == '#') continue;

                    // 원하는 문자가 아닌 경우
                    if (!isHigh[counter]) {
                        if (board[nx][ny] == '1') continue;
                    }
                    else {
                        if (board[nx][ny] != '1') continue;
                    }

                    // 이미 탐색한 경우
                    if (region[nx][ny] != 0) continue;

                    region[nx][ny] = counter;
                    q.push({ nx,ny });
                }
            }
        }
    }

    for (int idx = 0; idx < pos.size(); idx++) {
        int x = pos[idx].first;
        int y = pos[idx].second;

        for (int i = 0; i < 4; i++) {
            int j = (i + 2) % 4;
            int ax = x + dx[i];
            int ay = y + dy[i];
            int bx = x + dx[j];
            int by = y + dy[j];
            char curDir = dir[i];

            if (ax < 0 || ax >= n || ay < 0 || ay >= m) continue;
            if (bx < 0 || bx >= n || by < 0 || by >= m) continue;

            int ra = region[ax][ay];
            int rb = region[bx][by];

            if (!ra || !rb) continue; // 벽이나 ?인 경우
            if (isHigh[ra] && !isHigh[rb]) {
                bool duplicated = false;
                for (auto e : cands[idx]) {
                    if (e.a == ra && e.b == rb) {
                        duplicated = true;
                        break;
                    }
                }

                if (!duplicated) {
                    cands[idx].push_back({ curDir,ra,rb });
                }
            }
        }
    }

    for (int i = 1; i <= regionCounter; i++) {
        parent[i] = i;
    }

    for (auto e : tar) {
        hasTar[region[e.first][e.second]] = true;
    }

    cin >> sx >> sy;

    startRegion = Find(region[sx - 1][sy - 1]);

    if (tar.empty()) {
        cout << -1;
        return 0;
    }

    if (connected()) {
        printBoard();
        return 0;
    }

    dfs(0);
    cout << -1;
}

더 구체적으로 코드 흐름에 대해 살펴보자.

1
2
3
4
5
6
7

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		cin >> board[i][j];
		if (board[i][j] == '?') pos.push_back({ i,j });
		else if (board[i][j] == 'B' || board[i][j] == 'P') tar.push_back({ i,j });
	}
}

먼저 격자판을 초기화한다. pos 는 경사로를 설치할 지점의 좌표를 관리하며, tar 은 도착지의 좌표를 관리한다.

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

int regionCounter = 0;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (board[i][j] == '#' || board[i][j] == '?') continue;
		if (region[i][j] != 0) continue;

		int counter = ++regionCounter;
		region[i][j] = counter;
		isHigh[counter] = (board[i][j] == '1');
		queue<pair<int, int>> q;
		q.push({ i,j });

		while (!q.empty()) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			for (int idx = 0; idx < 4; idx++) {
				int nx = x + dx[idx];
				int ny = y + dy[idx];

				if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
				if (board[nx][ny] == '?' || board[nx][ny] == '#') continue;

				// 원하는 문자가 아닌 경우
				if (!isHigh[counter]) {
					if (board[nx][ny] == '1') continue;
				}
				else {
					if (board[nx][ny] != '1') continue;
				}

				// 이미 탐색한 경우
				if (region[nx][ny] != 0) continue;

				region[nx][ny] = counter;
				q.push({ nx,ny });
			}
		}
	}
}

격자판에서 연속된 고지대/저지대 영역을 그룹핑한다. 기존에는 고지대 영역 번호를 양수, 저지대 영역 번호를 음수로 설정하고, 이를 관리하기 위해 unordered_map 을 사용했으나, TLE이 발생했다. 이론적으로는 원소 접근 시간복잡도는 배열과 같은 $O(1)$이지만, 해시 충돌, 해시 계산, 캐시 locality, rehashing 등으로 인해 지정되는 원소가 증가할수록 배열에 비해 높은 오버헤드를 가지게 된다. 따라서 지대 높이를 영역 번호의 부호로 구분하지 않고 별도의 배열(isHigh)로 관리했다.

이런 점을 주의하며 BFS를 돌며 영역 번호를 결정하면 된다.

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

for (int idx = 0; idx < pos.size(); idx++) {
	int x = pos[idx].first;
	int y = pos[idx].second;

	for (int i = 0; i < 4; i++) {
		int j = (i + 2) % 4;
		int ax = x + dx[i];
		int ay = y + dy[i];
		int bx = x + dx[j];
		int by = y + dy[j];
		char curDir = dir[i];

		if (ax < 0 || ax >= n || ay < 0 || ay >= m) continue;
		if (bx < 0 || bx >= n || by < 0 || by >= m) continue;

		int ra = region[ax][ay];
		int rb = region[bx][by];

		if (!ra || !rb) continue; // 벽이나 ?인 경우
		if (isHigh[ra] && !isHigh[rb]) {
			bool duplicated = false;
			for (auto e : cands[idx]) {
				if (e.a == ra && e.b == rb) {
					duplicated = true;
					break;
				}
			}

			if (!duplicated) {
				cands[idx].push_back({ curDir,ra,rb });
			}
		}
	}
}

최적화 로직이다. 기존에는 위 로직을 DFS에 포함시켜 진행했는데, 불필요한 연산이 발생하기에, 경사로를 설치할 수 있는 경우만 따로 cands에 넣어, 이후 DFS에서 cands를 보고 경사로를 설치할 수 있도록 구현하였다.

1
2
3

for (auto e : tar) {
	hasTar[region[e.first][e.second]] = true;
}

hasTar은 해당 영역 번호에 목적지가 있는지를 저장한다. 출발지와 도착지가 연결되었는지 확인할 때, 해당 영역이 목적지를 포함하는지 확인하는 불필요한 탐색을 막을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int Find(int x) {
    while (parent[x] != x) x = parent[x];

    return x;
}

// 실제로 합쳐졌다면 true
bool Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);

    if (px == py) {
        history.push_back({ px,parent[px],rnk[px],hasTar[px] });
        history.push_back({ py,parent[py],rnk[py],hasTar[py] });
        return false;
    }
    if (rnk[px] < rnk[py]) swap(px, py);
    history.push_back({ px,parent[px],rnk[px],hasTar[px] });
    history.push_back({ py,parent[py],rnk[py],hasTar[py] });
    parent[py] = px;
    hasTar[px] = hasTar[px] || hasTar[py];
    if (rnk[px] == rnk[py]) rnk[px]++;
    return true;
}

Union Find는 rank 기반 Union Find를 사용한다. DFS 탐색을 마치고 롤백하기 위해 이전 상태를 기억해야 하는데, 경로 압축 기법을 사용하면 롤백할 수 없기 때문이다.

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

void dfs(int cnt) {
    if (cnt == pos.size()) {
        if (connected()) {
            printBoard();
            exit(0);
        }

        return;
    }

    if (cands[cnt].empty()) {
        dfs(cnt + 1);

        return;
    }

    int x = pos[cnt].first;
    int y = pos[cnt].second;

    for (auto e : cands[cnt]) {
        board[x][y] = e.dir;
        bool merged = Union(e.a, e.b);
        if (merged && connected()) {
            printBoard();
            exit(0);
        }

        dfs(cnt + 1);
        rollback();
        board[x][y] = '?';
    }
}

매 재귀마다 connected 메서드를 통해 연결 여부를 체크하며, 그런 경우 조기 종료한다.

Union 메서드는 실제로 영역이 합쳐졌는지 여부(merged)를 리턴하도록 하여, 불필요한 connected 메서드 호출을 막는다.

1
2
3
4
5
6
7
8
9
10
11

if (tar.empty()) {
	cout << -1;
	return 0;
}

if (connected()) {
	printBoard();
	return 0;
}

dfs(0);

DFS 호출 전 도착지가 없는지, 이미 연결되었는지 체크하여 불필요하게 DFS를 수행하는 것을 막는다.

시간복잡도

$N$을 행, $M$을 열, $K$를 ?의 개수라고 하자.

BFS를 수행하며 영역 번호를 지정하는데 $O(NM)$이다.

유효한 ? 방향을 계산하는 데 $O(K)$이다.

Union Find에서 Find 메서드의 시간복잡도는 $O(log(NM))$이고, DFS 탐색 상태 수는 최대 $2^K$이므로, DFS에서 $O(2^K \cdot log(NM))$이다.

따라서 전체 시간복잡도는 $O(NM+2^K \cdot log(NM))$이다.

공간복잡도

board, region 등과 같은 배열에서 $O(NM)$이며, 가장 지배적이다.

PS
baekjoon 백준 BFS DFS 너비우선탐색 깊이우선탐색 분리집합 UnionFind
This post is licensed under CC BY 4.0 by the author.