[정올 1912] 미로 탐색

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1185&sca=99&sfl=wr_hit&stx=1912 

JUNGOL

#include <stdio.h>

int N, M, s, e, cnt=1;
bool checked[100001];

struct Pair {
	int x, y;
} IA1[1000001], IA2[1000001];
struct Match {
	Match* pPrev;
	Match* pNext;
	int linked;
	Match(Match* prev, Match* next, int val) : pPrev(prev), pNext(next), linked(val) {
		if (prev != nullptr) prev->pNext = this;
		if (next != nullptr) next->pPrev = this;
	}
	Match() : pPrev(nullptr), pNext(nullptr), linked(-1) {}
	~Match() {
		if (pPrev)	pPrev->pNext = pNext;
		if (pNext)	pNext->pPrev = pPrev;
	}
} *pList, **pTailList;
struct Node {
	int PrevSiteIdx;
	int CurrSite;
	Node(int prev, int curr) : PrevSiteIdx(prev), CurrSite(curr) {}
	Node() : PrevSiteIdx(0), CurrSite(0) {}
};
Node BfsArr[100001*10];

void push_back(Node nd) {	BfsArr[e++] = nd;  }

int getNextSite(int site) {
	Match* pMy = pList[site].pNext;
	int result = -1;
	while (pMy) {
		if (checked[pMy->linked]) {
			Match* pTmp = pMy;
			pMy = pMy->pNext;
			delete pTmp;
		}
		else {
			result = pMy->linked;
			delete pMy;
			break;
		}
	}
	return result;
}

void mergesort(Pair* pSrc, Pair* pDst, int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;
	mergesort(pSrc, pDst, s, m);
	mergesort(pSrc, pDst, m + 1, e);

	int i = s, j = m + 1, k = s;

	while (i <= m && j <= e) {
		if (pSrc[i].x > pSrc[j].x)  pDst[k++] = pSrc[j++];
		else if ((pSrc[i].x == pSrc[j].x) && (pSrc[i].y >= pSrc[j].y))  pDst[k++] = pSrc[j++];
		else pDst[k++] = pSrc[i++];
	}

	while (i <= m) pDst[k++] = pSrc[i++];
	while (j <= e) pDst[k++] = pSrc[j++];

	for (i = s; i <= e; i++) pSrc[i] = pDst[i];
}

void input() {
	scanf("%d %d", &N, &M);
	pList = new Match[N + 1];
	pTailList = new Match*[N + 1];
	for (int i = 0; i < N + 1; i++) { //Tail을 지정
		pTailList[i] = &pList[i];
	}

	int a, b;
	for (int i = 0; i < M; i++)	{ //양방향으로 들어가야 하기 때문에 양쪽 다 넣는다.
		scanf("%d %d", &a, &b);
		IA1[2 * i].x = a; IA1[2 * i].y = b;
		IA1[2 * i + 1].x = b; IA1[2 * i + 1].y = a;
	}

	//mergesort
	mergesort(IA1, IA2, 0, 2 * M - 1);
	for (int i = 0; i < 2 * M; i++) {
		pTailList[IA1[i].x] = new Match(pTailList[IA1[i].x], pTailList[IA1[i].x]->pNext, IA1[i].y);
	}
}

void bfs() { //뒤로 돌아가는 걸 어떻게 해야할지
	while (s <= e) {
		Node my = BfsArr[s++];
		
		int nextsite = getNextSite(my.CurrSite);
		int prevsiteidx;
		
		if (nextsite == -1)	{ //방문할 곳이 없는 경우, 이전으로 돌아간다.
			nextsite = BfsArr[my.PrevSiteIdx].CurrSite;
			prevsiteidx = BfsArr[my.PrevSiteIdx].PrevSiteIdx;
		}
		else { //방문할 곳으로 방문한다.
			prevsiteidx = s - 1;
			checked[nextsite] = true;
			printf("%d ", nextsite);
			cnt++;
			if (cnt == N) break;
		}
		Node New(prevsiteidx, nextsite);
		push_back(New);
	}
}

int main(void) {
	input();
	Node my(-1, 1);
	checked[1] = true;
	printf("1 ");
	push_back(my);
	bfs();

	return 1;
}