설계:
- BFS 조건 만족시키기(mapping)
- BFS의 '비용=1' 조건을 만족시키기 위해 주어진 조각들의 map(pm)을 타일의 map(ts)에 대응시키기
- pm(idx = 조각 위치, pm[idx] = 조각번호), tn(idx = 조각 위치, tn[idx] = 타일번호)
- 2조각이 1타일에 대응되므로 pm과 동일한 크기의 tn배열 선언, 첫 2칸을 1로하고 2칸마다 1씩 증가
- pm상 모든 조각에 대해 2조각 씩 뛰어넘으며 이웃 조건 검사해 adj list 구성
- ts(idx = 타일번호, ts[idx] = 타일의 이웃 목록 => graph repr; adj list)
수정:
- 경로 출력하기
- qnode를 임의 메모리에 선언x 타일번호 tn으로 접근할 수 있도록 tn을 idx로 삼는 qnode 배열 선언
- qs(idx = 타일번호, qs[idx] = BFS queue에 올라간 idx 타일의 정보(qnode 구조체) 혹은 그 주소)
- qnode 구조체에 부모 pt 필드 추가하여 해당 qnode에 이르기까지의 경로를 역추적 가능케
- cd(자식)->pt(부모) = pt // pt는 포인터야 하며, 원본 qnode의 주소에 대한 포인터여야 한다. 원본 qnode를 scope밖(main 함수)에서도 사용하기 때문에 scope 밖에서도 유효하도록 new로 선언하도록 한다.(지역변수로 선언 x)
- 예외처리
- '이웃관계 탐색시 빈 조각(조각번호가 부여되지 않은)을 skip' 누락
- 이웃관계가 되려면 조각번호 동일해야한다는 조건을 누락
소요시간:
개선:
#include <stdio.h>
#include <queue>
using namespace std;
struct tile {
int nb[6];
};
struct qnode {
int tn;
struct qnode *pt;
};
// 시계 반대 방향
int di[] = { 1, 0, -1, -1, 0, 1 };
int dj[] = { 0, -1, 0, 0, 1, 0 };
#define IN_PMAP(i, j) (0 <= (i) && (i) < N && 0 <= (j) && (j) < 2 * N)
struct qnode *BFS(tile ts[], int no) { /* 실시간 변화 반영하려면 포인터에 대한 배열이어야 */
auto qs = new qnode[no + 1]; /* 타일번호 no는 1부터 시작 */ /* rt도 여기서 주소 가져와야 */
qnode *rt = qs + 1;
rt->tn = 1, rt->pt = NULL;
bool v[250001] = { 0 };
v[1] = 1; /* bfs 내 visited 위치 */
queue<qnode *> q;
q.push(rt);
while (!q.empty()) {
qnode *pt = q.front();
q.pop();
for (int d = 0; d < 6; ++d) {
int cd_tn = ts[pt->tn].nb[d];
if (cd_tn == 0) /* 조건 누락 */
continue;
if (v[cd_tn])
continue;
v[cd_tn] = 1;
qnode *cd = qs + cd_tn;
cd->tn = cd_tn, cd->pt = pt; /* cd.pt = &pt; 지역 변수 pt(pt = q.front();)에 대한 주소를 넣으면 x 해당 scope 벗어나면 pt의 내용은 무효해짐 */
q.push(cd);
}
}
return qs;
}
int main() {
int N;
scanf("%d", &N);
// piece map(pm, 2차원 배열)와 tiles(ts, 1차원 배열)의 연결
// piece의 배열에 맞게 tile을 배열(tm, 2차원 배열)
// tm에 tiles 대응시키기
int pm[500][1000] = { 0 }, tn[500][1000] = { 0 };
int no = 1;
for (int i = 0; i < N; ++i) {
int jb, je; /* 홀짝 바뀜 */
if (i % 2) { jb = 1, je = 2 * N - 1; }
else { jb = 0, je = 2 * N; }
for (int j = jb; j < je; j += 2) {
scanf("%d%d", pm[i] + j, pm[i] + j + 1);
tn[i][j] = tn[i][j + 1] = no++;
}
}
struct tile ts[250001] = { 0 }; // idx 1부터 시작, 연결 안 되어 있으면 이웃 tile no가 0임
for (int i = 0; i < N; ++i) {
int jb, je;
if (i % 2) { jb = 1, je = 2 * N - 1; }
else { jb = 0, je = 2 * N; }
for (int j = jb; j < je;) { /* j에 대한 increment는 헷갈리니까 한꺼번에 x */
int n = 0;
for (; n < 3; ++n) { // 타일의 첫번째 조각
int ni = i + di[n], nj = j + dj[n];
if (!IN_PMAP(ni, nj) || !pm[ni][nj]) /* 거르는 조건은 ||로 묶기 */
continue;
if (pm[i][j] == pm[ni][nj]) /* 조건 누락*/
ts[tn[i][j]].nb[n] = tn[ni][nj];
}
++j;
for (; n < 6; ++n) { // 타일의 두번째 조각
int ni = i + di[n], nj = j + dj[n];
if (!IN_PMAP(ni, nj) || !pm[ni][nj])
continue;
if (pm[i][j] == pm[ni][nj]) /* 조건 누락*/
ts[tn[i][j]].nb[n] = tn[ni][nj];
}
++j;
}
}
qnode *qn = BFS(ts, no);
int i;
for (i = no - 1; i >= 1; --i) /* 경로 출력은 부모와의 link를 통해서(qnode 구조체의 pt필드) */
if (qn[i].pt)
break;
int v[250001], j = 0;
for (qnode *q = qn + i; q; q = q->pt, ++j)
v[j] = q->tn;
printf("%d\n", j);
for (--j; j >= 0; --j)
printf("%d ", v[j]);
return 0;
}