BOJ 14737 Dev, Please Add This!

문제 요약

격자에서 공을 굴려 별을 먹는 게임을 합니다. 공은 벽에 닿을 때까지 멈추지 않습니다. 모든 별을 먹는 것이 가능한지 판별하세요.

풀이

일단 공의 움직임이 단방향 간선으로 표현되니까 SCC를 고려합니다. 같은 SCC 안에 있는 칸은 마음대로 왔다갔다 할 수 있으니까 한 정점으로 취급하기 위함입니다.

단방향 간선 그래프의 SCC들을 한 정점으로 취급하면 전체 그래프는 DAG가 됩니다. 여기서 시작점이 포함된 SCC에서 도달할 수 있는 정점이 있을 것이고, 도달할 수 없는 정점도 있을 것이고, 두 정점을 동시에 방문할 수 없는 경우도 있을 거에요.

격자 위에서 SCC는 위아래나 양옆이 벽으로 막혀 있어서 마음대로 왔다갔다할 수 있는 길의 모습을 합니다. 어떤 SCC를 방문했다면 그 SCC에 해당하는 길 위에 놓인 모든 별을 먹을 수 있겠죠(실제 SCC에 포함되는 건 길이 꺾이고 끝나는 지점들뿐임에 유의합시다).

어떤 별을 기준으로 생각하면, 그 별을 좌우로 지나는 길과 상하로 지나는 길이 정확히 하나씩 존재합니다. 각각의 길은 하나의 SCC에 배정되므로, 어떤 별을 먹기 위해서는 최대 두 SCC 중 적어도 하나는 방문할 필요가 있다는 결론을 얻습니다.

문제에서 요구하는 바에 따라 확인해야 하는 모든 조건을 얻었는데, 전부 $p \vee q$ 꼴을 $\wedge$로 연결한 모양입니다. 그러니 SCC의 방문 여부에 대한 2-SAT을 수행하면 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int dy[] = {-1,0,1,0}, dx[] = {0,-1,0,1};
inline int notx(int x){return x^1;}
inline int truex(int x){return x<<1;}
inline int falsex(int x){return x<<1|1;}
inline int zip(int y, int x){return (y-1)*50+x;}

vector<int> e[5050], se[2525];
int scc[5050], num[5050], low[5050];
bool svis[2525][2525];
stack<int> stk;
int cnt, s;
char board[60][60];

void dfs(int now){
	stk.push(now);
	num[now] = ++cnt;
	low[now] = cnt;
	for(auto nxt : e[now]){
		if(!num[nxt]){
			dfs(nxt);
			low[now] = min(low[now], low[nxt]);
		}
		else if(!scc[nxt]) low[now] = min(low[now], num[nxt]);
	}
	
	if(low[now] == num[now]){
		s++;
		while(stk.size()){
			int x = stk.top(); stk.pop();
			scc[x] = s;
			if(now == x) break;
		}
	}
}

void addCond(int x1, int x2){
	e[notx(x1)].push_back(x2);
	e[notx(x2)].push_back(x1);
}

void sdfs(int root, int now){svis[root][now] = 1; for(auto& nxt : se[now]) if(!svis[root][nxt]) sdfs(root, nxt);}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	memset(board, '#', sizeof(board)); int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> board[i][j];
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(board[i][j] != '#') for(int dir = 0; dir < 4; dir++){
		int ni = i, nj = j; while(board[ni][nj] != '#') ni += dy[dir], nj += dx[dir];
		ni -= dy[dir]; nj -= dx[dir]; if(ni != i || nj != j) e[zip(i, j)].push_back(zip(ni, nj));
	} 
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(!num[zip(i, j)]) dfs(zip(i, j));
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){for(auto& nxt : e[zip(i, j)]) if(scc[zip(i, j)] != scc[nxt]) se[scc[zip(i, j)]].push_back(scc[nxt]); e[zip(i, j)].clear();}
	for(int i = 1; i <= s; i++){sdfs(i, i); for(int j = 1; j < i; j++) if(!svis[i][j] && !svis[j][i]) addCond(falsex(i), falsex(j));}
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
		if(board[i][j] == 'O'){int st = scc[zip(i, j)]; addCond(truex(st), truex(st)); for(int i = 1; i <= s; i++) if(!svis[st][i]) addCond(falsex(i), falsex(i));}
		else if(board[i][j] == '*'){
			int nxt[2]; for(int dir = 0; dir < 2; dir++){
				int ni = i, nj = j; while(board[ni][nj] != '#') ni += dy[dir], nj += dx[dir];
				ni -= dy[dir]; nj -= dx[dir]; nxt[dir] = scc[zip(ni, nj)];		
			}
			addCond(truex(nxt[0]), truex(nxt[1]));
		}
	}
	while(stk.size()) stk.pop(); memset(scc, 0, sizeof(scc)); memset(num, 0, sizeof(num)); memset(low, 0, sizeof(low)); cnt = 0; int S = s; s = 0;
	for(int i = truex(1); i <= falsex(S); i++) if(!num[i]) dfs(i);
	for(int i = 1; i <= S; i++) if(scc[truex(i)] == scc[falsex(i)]) return !(cout << "NO");
	cout << "YES";
}