주어진 문자들을 어떻게 노드로 정의할 것이며, 어떻게 자료구조를 설정할 것인지 물어보는 문제.
단순 최단경로 알고리즘을 사용한다면 별다를 문제는 없다.
문제에서는 타일은 두 개의 숫자로 이루어진다. 두 개의 숫자는 각자 '칸'을 의미하며 최대가 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;
}