문제:
17244번: 아맞다우산
경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등
www.acmicpc.net
설계:
모든 물건들을 방문할 때까지 BFS vs 물건들의 순열에 대해 BFS
둘을 놓고 고민하다가 후자를 선택했다.
물건들의 순열에 대해 BFS
순열에서 이웃한 쌍의 물건 중 전자를 source, 후자를 destination으로 놓고 BFS를 수행했다.
전자에서 후자로 가는 길에 다른 물건을 방문했고, 이 물건에 대해 아직 BFS를 수행하지 않았다면,
현 BFS에서 이미 방문했으므로, 이 물건에 대한 BFS 수행을 방지해야 한다고 생각했다.
search로 최소 경로를 찾으면서 도중에 방문한 물건들의 목록도 찾으려면
분기마다의 자료구조 점층 누적 및 점층 복구가 가능한 DFS를 수행해야 했다.
순열 : ... X1 X3 ...
map: XOOOXOX
(왼쪽 X부터 X1, X2, X3)
가령, 순열상 인접한 X1과 X3에 대해 BFS를 수행하면 X2를 도중에 방문하게 된다.
따라서 X1->X3을 구하는 대신 X1->X2->X3를 구해야 된다고 생각하고 탐색법을 DFS로 변경했다.
하지만 이미 순열 부분에서 모든 X들의 모든 순열을 구했고, BFS에서 최단거리를 구했기에,
순열 : ...X1 X2 X3... 에 의해 위 가능성은 커버된다.
뿐만 아니라 DFS는 최단거리를 구하는 것이 아니기 때문에 사용하면 안 된다.
Program Step
모든 물건들을 방문할 때까지 BFS : 50 * 50 * 5! (2068kb, 0ms)
물건들의 순열에 대해 BFS : C(5, 2) * 50 * 50 + 5! (2004kb, 0ms)
코드:
모든 물건들을 방문할 때까지 BFS
#include <iostream>
#include <queue>
using namespace std;
int N, M;
char map[50][50];
pair<int, int> str, ext;
int xn;
bool vst[50][50][1 << 5];
int all;
struct qnode {
int r, c, b;
};
queue<qnode> q;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> M >> N;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < M; ++c) {
cin >> map[r][c];
switch (map[r][c]) {
case 'S': vst[r][c][0] = 1; q.push({ r, c }); break;
case 'E': ext = make_pair(r, c); map[r][c] = '#'; break;
case 'X': map[r][c] = xn++; break;
}
}
}
all = (1 << xn) - 1;
int ans = 0;
while (!q.empty()) {
int qs = q.size();
while (qs--) {
qnode pt = q.front(); q.pop();
if (pt.b == all) {
for (int d = 0; d < 4; ++d) {
int nr = pt.r + dr[d], nc = pt.c + dc[d];
if (make_pair(nr, nc) == ext) {
goto out;
}
}
}
for (int d = 0; d < 4; ++d) {
int nr = pt.r + dr[d], nc = pt.c + dc[d];
int ch = map[nr][nc];
int nb = pt.b;
if (ch <= 5) {
nb = nb | (1 << ch);
}
if (ch == '#' || vst[nr][nc][nb]) {
continue;
}
vst[nr][nc][nb] = 1;
q.push({ nr, nc, nb });
}
}
++ans;
}
out:
cout << ans + 1;
return 0;
}물건들의 순열에 대해 BFS
/* queue는 clear가 불가하므로, 지역변수로 선언하기 */
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M;
char map[50][50];
pair<int, int> str, ext;
vector<pair<int, int>> obj, vtx;
int cst[7][7];
int vst[49][49], v;
int pmt[7];
struct qnode {
int r, c;
};
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
#define IN(r, c) (0 <= (r) && (r) < N && 0 <= (c) && (c) < M)
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> M >> N;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < M; ++c) {
cin >> map[r][c];
switch (map[r][c]) {
case 'S': str = make_pair(r, c); break;
case 'E': ext = make_pair(r, c); break;
case 'X': obj.emplace_back(r, c); break;
}
}
}
vtx.push_back(str);
vtx.insert(vtx.end(), obj.begin(), obj.end());
vtx.push_back(ext);
for (int i = 0; i < vtx.size() - 1; ++i) {
for (int j = i + 1; j < vtx.size(); ++j) {
vst[vtx[i].first][vtx[i].second] = ++v;
queue<qnode> q; /* 1 */
q.push({ vtx[i].first, vtx[i].second });
int c = 0;
while (!q.empty()) {
int qs = q.size();
while (qs--) {
qnode pt = q.front(); q.pop();
if (make_pair(pt.r, pt.c) == vtx[j])
goto out;
for (int d = 0; d < 4; ++d) {
int nr = pt.r + dr[d], nc = pt.c + dc[d];
if (!IN(nr, nc) || map[nr][nc] == '#' || vst[nr][nc] == v)
continue;
vst[nr][nc] = v;
q.push({ nr, nc });
}
}
++c;
}
out:
cst[i][j] = cst[j][i] = c;
}
}
for (int e = 0; e < vtx.size(); ++e) {
pmt[e] = e;
}
int ans = 17500;
do {
int c = 0;
for (int e = 0; e < vtx.size() - 1; ++e)
c += cst[pmt[e]][pmt[e + 1]];
if (c < ans)
ans = c;
} while (next_permutation(pmt + 1, pmt + vtx.size() - 1));
cout << ans;
return 0;
}
새로 배운점:
level-order BFS
queue<qnode> q; // queue는 clear불가, 지역으로 선언할 것!
while(!q.empty()){
// level별 전처리
int qs = q.size();
while(qs--){
// 기존 BFS와 동일
}
// level별 후처리(e.g. ++ans)
}