취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5570번 문제인 산타클로스와 루돌프이다.

문제는 아래 링크를 확인하자.

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

문제에서 주어진 산타의 방문순서를 거꾸로 뒤집은 순서의 경우의 수를 구하자. 즉, 매 집에서 상하좌우 방향으로 이동하면서 (존재한다면) 가장 먼저 나오는 방문하지 않은 집에 방문하는 것을 반복하고 다시 교회로 돌아오는 경우의 수를 구하자.

매 집에서 상하좌우를 하나 택해 바로 인 순서대로 방문하는 경우의 수인 4^23은 굉장히 큰 수이므로 이러한 경우의 수를 하나하나 직접 탐색하는 것은 쉽지 않을 것이라 짐작할 수 있다. (실제로는 방문에 제약(같은 행 또는 열에 있는 집으로만 이동 가능)이 있으므로 4^23보다는 적은 경우의 수가 나오겠지만 그 bound가 어느 정도일지는 생각해 보진 않았다.)

대신, 각 집의 방문여부는 2^23 = 8388608가지 존재하고, 각 방문 여부마다 가장 마지막에 들린 좌표의 경우의 수는 23가지 존재하므로 제한시간(12초) 내에 위의 케이스들을 한번씩 접근하는 것은 가능할 것이다. 이 때 i번째 집의 방문 여부를 i번째 비트의 0과 1로 비트마스킹하면 코드의 작동을 최적화할 수 있다.

위의 각 케이스들은 "방문한 집의 수가 늘어나는 순"으로 살피면서 경우의 수를 누적해나가야 한다. 이는 BFS 순과 같으므로 BFS와 같은 순서대로 각 케이스에 접근하자.

위 풀이에 bidirctional search까지 적용(한쪽은 산타가 선물을 놓고 가는 순서, 다른 쪽은 경로의 역순으로 탐색)하면 시간복잡도를 더욱 낮출 수 있을 것으로 추측한다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int R, C;
int RR, CC; // 교회 좌표
int cnt = 0;
int arr[12][12];


vector<int> dirR[11][11];
vector<int> revR[11][11];
vector<int> dirC[11][11];
vector<int> revC[11][11];

map<int, int> btor, btoc;
map<pair<int, pair<int, int>>, int> mp; // (방문비트,(최종위치)) -> 경우의수

void bfs() {
	mp.insert(make_pair(make_pair(0, make_pair(RR,CC)), 1));
	queue<pair<int, pair<int, int>>> que;
	que.push(make_pair(0, make_pair(RR, CC)));
	while (!que.empty()) {
		int cur = que.front().first, r = que.front().second.first, c = que.front().second.second;
		if (cur == (1 << cnt) - 1) return;
		que.pop();

		for (auto& x : dirR[r][c]) {
			if (cur & x) continue;
			if (mp.find(make_pair((cur | x), make_pair(btor[x], btoc[x]))) == mp.end()) {
				mp.insert(make_pair(make_pair((cur | x), make_pair(btor[x], btoc[x])), mp[make_pair(cur, make_pair(r, c))]));
				que.push(make_pair((cur | x), make_pair(btor[x], btoc[x])));
			}
			else {
				mp[make_pair((cur | x), make_pair(btor[x], btoc[x]))] += mp[make_pair(cur, make_pair(r, c))];
			}
			break;
		}
		for (auto& x : revR[r][c]) {
			if (cur & x) continue;
			if (mp.find(make_pair((cur | x), make_pair(btor[x], btoc[x]))) == mp.end()) {
				mp.insert(make_pair(make_pair((cur | x), make_pair(btor[x], btoc[x])), mp[make_pair(cur, make_pair(r, c))]));
				que.push(make_pair((cur | x), make_pair(btor[x], btoc[x])));
			}
			else {
				mp[make_pair((cur | x), make_pair(btor[x], btoc[x]))] += mp[make_pair(cur, make_pair(r, c))];
			}
			break;
		}
		for (auto& x : dirC[r][c]) {
			if (cur & x) continue;
			if (mp.find(make_pair((cur | x), make_pair(btor[x], btoc[x]))) == mp.end()) {
				mp.insert(make_pair(make_pair((cur | x), make_pair(btor[x], btoc[x])), mp[make_pair(cur, make_pair(r, c))]));
				que.push(make_pair((cur | x), make_pair(btor[x], btoc[x])));
			}
			else {
				mp[make_pair((cur | x), make_pair(btor[x], btoc[x]))] += mp[make_pair(cur, make_pair(r, c))];
			}
			break;
		}
		for (auto& x : revC[r][c]) {
			if (cur & x) continue;
			if (mp.find(make_pair((cur | x), make_pair(btor[x], btoc[x]))) == mp.end()) {
				mp.insert(make_pair(make_pair((cur | x), make_pair(btor[x], btoc[x])), mp[make_pair(cur, make_pair(r, c))]));
				que.push(make_pair((cur | x), make_pair(btor[x], btoc[x])));
			}
			else {
				mp[make_pair((cur | x), make_pair(btor[x], btoc[x]))] += mp[make_pair(cur, make_pair(r, c))];
			}
			break;
		}
		mp.erase(make_pair(cur, make_pair(r, c)));
	}
}

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

	cin >> C >> R;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			int& tmp = arr[r][c];
			cin >> tmp;
			if (tmp == 1) {
				tmp <<= cnt++;
				btor.insert(make_pair(tmp, r));
				btoc.insert(make_pair(tmp, c));
			}
			else if (tmp == 2) {
				tmp = 0;
				RR = r, CC = c;
			}
		}
	}

	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {

			for (int rr = r + 1; rr <= R; rr++) {
				if (arr[rr][c]) dirR[r][c].emplace_back(arr[rr][c]);
			}
			for (int rr = r - 1; rr > 0; rr--) {
				if (arr[rr][c]) revR[r][c].emplace_back(arr[rr][c]);
			}
			for (int cc = c + 1; cc <= C; cc++) {
				if (arr[r][cc]) dirC[r][c].emplace_back(arr[r][cc]);
			}
			for (int cc = c - 1; cc > 0; cc--) {
				if (arr[r][cc]) revC[r][c].emplace_back(arr[r][cc]);
			}
		}
	}

	bfs();

	int ans = 0;
	for (auto x : dirR[RR][CC]) {
		if (mp.find(make_pair((1 << cnt) - 1, make_pair(btor[x], btoc[x]))) != mp.end()) ans += mp[make_pair((1 << cnt) - 1, make_pair(btor[x], btoc[x]))];
	}
	for (auto x : revR[RR][CC]) {
		if (mp.find(make_pair((1 << cnt) - 1, make_pair(btor[x], btoc[x]))) != mp.end()) ans += mp[make_pair((1 << cnt) - 1, make_pair(btor[x], btoc[x]))];
	}
	for (auto x : dirC[RR][CC]) {
		if (mp.find(make_pair((1 << cnt) - 1, make_pair(btor[x], btoc[x]))) != mp.end()) ans += mp[make_pair((1 << cnt) - 1, make_pair(btor[x], btoc[x]))];
	}
	for (auto x : revC[RR][CC]) {
		if (mp.find(make_pair((1 << cnt) - 1, make_pair(btor[x], btoc[x]))) != mp.end()) ans += mp[make_pair((1 << cnt) - 1, make_pair(btor[x], btoc[x]))];
	}

	cout << ans;
}