문제
BOJ 15455(https://www.acmicpc.net/problem/15455)
$n \cdot m$ 크기의 맵이 주어진다.
이 맵에는 걸어갈 수 있는 곳 . 벽으로 막힌 곳 # 사람의 시작 위치 A 박스의 시작 위치 B가 주어진다.
그 후 $q$개의 쿼리가 주어지는데, $A$가 박스 $B$를 밀고 갈 때 해당 주어진 쿼리의 위치로 박스를 옮길 수 있는지를 출력해야 한다.
이 때, 박스를 민다는 것은, $A$가 박스의 바로 옆(혹은 위, 아래)에 붙어서 $A \rightarrow B$방향으로 박스를 민다는 것이다.
풀이
꽤나 복잡한 그래프 문제이다.
일단 박스가 스스로 움직이는게 아닌, 사람이 밀어줘야 한다는 제약조건이 크다.
차근차근 생각해보면, 일단 그래프의 탐색 공간은 박스가 각 셀에 위치할 경우 각각이 공간이 되니까 $O(n \cdot m)$이다.
그러나, 박스 뿐만 아니라 현재 사람의 위치도 고려해야 한다.
해당 셀에서 박스 주변 4방향 중 사람이 현재 어디있는지를 추가적으로 저장해야 하므로, 총 탐색공간은 $4 \cdot n \cdot m$일 것이다.
이제 초기 위치에서부터 갈 수 있는 모든 탐색 공간을 BFS로 탐사하면 되는데, 현재 공간에서 다음 공간으로 이동할 수 있는지 여부를 아는 것이 중요하다.
현재 $(y, x)$에 박스가 있고 사람이 박스 주변의 $d$방향에 있을 때 박스에 인접한 다음 위치 $(ny, nx)$와 해당 위치로 밀고 가기 위한 사람의 방향 $nd$로 갈 수 있을까?
위에 대한 대답을 빠르게 들어야 하는데, 위의 문제를 정리해서 생각하면, 다음 두 가지를 만족해야 한다는 것을 알 수 있다.
- 애초에 $(ny, nx)$가 벽이 아닌가?
- 현재 사람의 위치 $(y, x)$의 $d$방향에서 다음 위치로 밀고 가기 위한 방향 $(y, x)$의 $nd$방향으로 사람이 움직일 수 있는가?
$1$번에 대한 답은 쉽게 구할 수 있는데, $2$번이 문제다.
$2$번을 조금 더 간략화하면 다음과 같다.
그래프에서 $(y, x)$를 거치지 않는 두 정점 사이의 path가 존재하는가?
일단 두 정점이 서로 다른 connected component에 존재할 경우 경로가 존재하지 않는다는 것은 자명하다.
문제는 두 정점이 하나의 connected component에 존재할 때 $(y, x)$를 지나지 않는 path가 존재하는지를 알아야 한다는 것인데, 이것을 위해서 DFS Spanning Tree에 대한 이해가 필요하다.
무향그래프에서 DFS Spanning Tree를 만들었을 때 원래 그래프의 간선들은 트리 간선 혹은 역 간선 둘 중 하나로 분류 된다.
방향 그래프에서 교차 간선과 순 간선이 추가적으로 존재한다는 것에 비해 생각할 것이 훨씬 적어진다.
위 그림은 간선 분류에 대한 이해를 돕기 위한 그림인데, 방향 그래프이고 탐색 순서는 $1 \rightarrow 3 \rightarrow 5 \rightarrow 4 \rightarrow 2$ 이다.
만약 방향성이 없는 그래프라면 교차 간선과 순 간선은 절대 존재하지 않는다.
순 간선은 곧 역 간선이라고 볼 수 있고, 교차 간선 같은 경우는 $u \rightarrow v$가 교차 간선이려면 $u$, $v$가 조상, 자손 관계가 아니면서 $v$의 dfs가 이미 끝난 상태에서 $u$의 dfs에서 $v$를 방문하면서 생기게 된다.
그러나 무향그래프에서는 $v$의 dfs 상태에서 $u$를 방문하지 않았을 리 없고, 결과적으로 교차 간선이 생긴다는 것은 모순이다.
아무튼 그래프에서 $x$를 지나지 않는 $path(u \rightarrow v)$가 존재하는지($cango(u, v, x)$) 확인하려면, 우선 DFS Spanning Tree를 생성해야 한다.
그 후 트리의 각 정점마다 “$subtree(node)$에서 최대로 조상으로 올라갈 수 있는 역간선 = $up[node]$”을 절단점 구하기 알고리즘을 약간 변형한 방법으로 모두 구해놓는다.
이제 실제로 $cango(u, v, x)$를 계산해야 하는데, $t = lca(u, v)$를 구하고 만약 $x$가 $path(t, u)$ 혹은 $path(t, v)$ 사이에 존재하지 않는다면 무조건 가능한 경우이다.
만약 $t=x$라면, $path(t, u)$중 $t$의 자식인 정점을 $child(t, u)$라고 할 때, $up[child(t, u)]$와 $up[child(t, v)]$ 모두 $x$보다 조상 노드로 갈 수 있어야 한다.
만약 $t \ne x$라면, $up[child(t, u\ or\ v)]$가 $x$보다 조상 노드로 갈 수 있어야 한다.
$cango(u, v, x)$를 계산할 수 있게 되었으니 이것을 이용해 bfs를 통해 Flood Fill과 비슷하게 갈 수 있는 곳들을 체크해주고, 쿼리에서는 그 결과값만을 출력해주면 된다.
소스코드
##include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 1501, MAXV = MAXN*MAXN, LOGN = 23;
const int dy[4] = { 0, 0, -1, 1 }, dx[4] = { -1, 1, 0, 0 };
int n, m, nv, qq, did, ay, ax, by, bx, vis[MAXV], dep[MAXV], up[MAXV], par[MAXV][LOGN], chk[MAXV][4];
string mp[MAXN];
vi g[MAXV];
void input() {
cin >> n >> m >> qq;
FOR(i, 0, n) cin >> mp[i];
}
int uidx(int y, int x) { return y*m+x; }
bool valid(int y, int x) { return 0 <= y && y < n && 0 <= x && x < m; }
// y, x를 root로 하는 하나의 컴포넌트로 이어진 그래프의 dfs 스패닝 트리를 만든다.
void getComponent(int y, int x) {
FOR(dir, 0, 4) {
int ny = y + dy[dir], nx = x + dx[dir];
if(valid(ny, nx) && mp[ny][nx] != '#') {
g[uidx(y, x)].pb(uidx(ny, nx));
if(par[uidx(ny, nx)][0] == -1) {
par[uidx(ny, nx)][0] = uidx(y, x);
getComponent(ny, nx);
}
}
}
}
// dfs 스패닝 트리에서 각 node마다 vis 부여하고 최대로 갈 수 있는 역간선을 구한다.
int dfs(int u) {
int ret = vis[u] = did++;
for(auto v : g[u]) {
if(par[v][0] == u) {
dep[v] = dep[u] + 1;
ret = min(ret, dfs(v));
} else ret = min(ret, vis[v]);
}
return up[u] = ret;
}
// dfs 스패닝 트리에서 u, v의 lca
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int dif = dep[u] - dep[v];
FOR(i, 0, LOGN) if(dif & (1<<i)) u = par[u][i];
if(u != v) {
RFOR(i, LOGN-1, 0) {
if(par[u][i] != par[v][i]) {
u = par[u][i], v = par[v][i];
}
}
u = par[u][0];
}
return u;
}
// u가 v의 자식일 때 path(u->v) 중 v의 자식을 반환
int getchild(int u, int v) {
int dif = dep[u] - dep[v];
for(int i = 1; dif != 1; ++i) {
if(dif&(1<<i)) dif -= (1<<i), u = par[u][i];
}
return u;
}
// x정점을 지나지 않고 u->v를 갈 수 있는지?
// x != u, v인 것만 넣기!!
// 무향 그래프에서는 무조건 역간선만 존재
bool cango(int u, int v, int x) {
if(par[u][0] == -1 || par[v][0] == -1) return false; // 시작 끝 둘 중 하나라도 같은 컴포넌트가 아니면 불가
if(par[x][0] == -1) return true; // 같은 컴포넌트인데 방해꾼이 없으면 가능
int t = lca(u, v);
if(x == t) { // t 자체가 잘리면? xuchild, xvchild->par[x]가 존재하는지 확인
return up[getchild(u, x)] < vis[x] && up[getchild(v, x)] < vis[x];
} else if(vis[t] <= vis[x] && vis[x] <= vis[u]) { // t->u사이가 잘리면? xuchild->par[x]가 존재하는지 확인
return up[getchild(u, x)] < vis[x];
} else if(vis[t] <= vis[x] && vis[x] <= vis[v]) { // t->v사이가 잘리면? xvchild->par[x]가 존재하는지 확인
return up[getchild(v, x)] < vis[x];
}
return true;
}
int solve() {
nv = n*m;
memset(par, -1, sizeof(par));
FOR(y, 0, n) {
FOR(x, 0, m) {
if(mp[y][x] == 'A') {
par[uidx(y, x)][0] = uidx(y, x);
ay = y, ax = x;
getComponent(y, x);
}
if(mp[y][x] == 'B') by = y, bx = x;
}
}
FOR(j, 1, LOGN) {
FOR(i, 0, nv) {
par[i][j] = par[par[i][j-1]][j-1];
}
}
dfs(uidx(ay, ax));
queue<ii> q;
FOR(dir, 0, 4) {
int ny = by - dy[dir], nx = bx - dx[dir]; // 상자를 그 방향으로 밀 수 있는 위치로 이동
if(valid(ny, nx) && cango(uidx(ay, ax), uidx(ny, nx), uidx(by, bx))) q.push({ uidx(by, bx), dir }), chk[uidx(by, bx)][dir] = 1;
}
while(q.size()) {
int u = q.front().first, d = q.front().second; q.pop();
int y = u/m, x = u%m, cy = y - dy[d], cx = x - dx[d]; // 현재 박스 위치, 현재 미는 곳 위치
FOR(dir, 0, 4) {
int py = y - dy[dir], px = x - dx[dir]; // 밀 수 있는 곳으로 가야 함.
if(dir == d || (valid(py, px) && cango(uidx(cy, cx), uidx(py, px), uidx(y, x)))) { // 해당 방향으로 밀 수 있으면
int ny = y + dy[dir], nx = x + dx[dir];
if(valid(ny, nx) && mp[ny][nx] != '#' && !chk[uidx(ny, nx)][dir]) {
chk[uidx(ny, nx)][dir] = 1;
q.push({ uidx(ny, nx), dir });
}
}
}
}
while(qq--) {
int y, x; cin >> y >> x; --y, --x;
if(y == by && x == bx) {
cout << "YES" << ENDL;
continue;
}
bool ans = false;
FOR(dir, 0, 4) {
if(chk[uidx(y, x)][dir]) {
ans = 1;
break;
}
}
if(ans) cout << "YES" << ENDL;
else cout << "NO" << ENDL;
}
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //