BOJ 5213 - TOTEM (과외맨)

* BOJ 5213 - TOTEM (과외맨)

  [ 분류 - BFS,DFS / 기타 최단경로 알고리즘 ]

  주어진 문자들을 어떻게 노드로 정의할 것이며, 어떻게 자료구조를 설정할 것인지 물어보는 문제.

  단순 최단경로 알고리즘을 사용한다면 별다를 문제는 없다.

  문제에서는 타일은 두 개의 숫자로 이루어진다. 두 개의 숫자는 각자 '칸'을 의미하며 최대가 6이다. 인접한 타일과 같은 숫자로 접점이 있다면 두 타일은 이어져 있다고 볼 수 있다.

  * 접근 방식

  1. 각 타일은 2개의 칸이고, 각 칸의 최대가 6이므로 두자리 수 하나로 퉁칠 수 있다.

  2. 입력으로 주어지는 순서는 맨위 좌측 타일부터 맨 아래 우측 타일까지를 주어주므로 indexing 절차가 필요함을 알 수 있다. 즉, 단순 2차원 배열로 두고 접근할 수 없으므로, offset(각 행에 대한 열의 수)을 두어 처리할 수 있다.

  3. 2.번까지 완료했다면 이제 인접하는지 알아내기 위해 타일에 해당하는 수에 대해 처리한다.

    3-1. 현재 타일과 좌측 아래 타일 그림에서의 (1)

    3-2. 현재 타일과 우측 아래 타일 그림에서의 (2)

    이 과정에서는 좌측 또는 우측 아래 타일이 없을 수 있으므로 범위 확인을 반드시 해야한다.

    3-1과 3-2는 수 비교이기 때문에 상수 시간에 판단이 가능하다.

- 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_V = 250001;
int p[MAX_V], cnt;
void trace(int u) {
	cnt++;
	if (p[u] != u)
		trace(p[u]);
	else printf("%d\n", cnt);
	printf("%d ", u + 1);
}
int main() {
	memset(p, -1, sizeof p);
	int N, i, j, a, b, s, e, ns, ne, nofs, ofs, u, tot, dnxt; // ofs : offset
	scanf("%d", &N);
	tot = N*N - (N / 2);
	vector<int> tile;
	vector<vector<int>> adj(tot);
	for (i = 0; i<tot; i++) {
		scanf("%d%d", &a, &b);
		a = a * 10 + b;
		tile.push_back(a);
	}
	ns = s = 0;
	ne = e = ofs = N;
	for (i = 0; i<N; i++) {
		nofs = i % 2 ? N : N - 1;
		ns = e;
		ne += nofs;
		for (j = s; j<e - 1; j++) {
			if (tile[j] % 10 == tile[j + 1] / 10) {
				adj[j].push_back(j + 1);
				adj[j + 1].push_back(j);
			}
		}

		if (i != N - 1) {
			for (j = s; j<e; j++) {
				dnxt = j + ofs + (i % 2);
				// 우측 하단
				if (ns <= dnxt && dnxt < ne && ((tile[j] % 10) == (tile[dnxt] / 10))) {
					adj[j].push_back(dnxt);
					adj[dnxt].push_back(j);
				}

				dnxt = j + ofs - !(i%2);
				// 좌측 하단
				if (ns <= dnxt && dnxt < ne && ((tile[j] / 10) == (tile[dnxt] % 10))) {
					adj[j].push_back(dnxt);
					adj[dnxt].push_back(j);
				}
			}
		}
		s = ns, e = ne, ofs = nofs;
	}
	queue<int> q;
	q.push(0);
	p[0] = 0;
	while (!q.empty()) {
		u = q.front(), q.pop();
		for (int& v : adj[u]) {
			if (p[v] == -1) {
				p[v] = u;
				q.push(v);
			}
		}
	}
	for (i = tot; i >= 0; i--) if (p[i] != -1) {
		trace(i);
		break;
	}
	return 0;
}