์•Œ๊ณ ๋ฆฌ์ฆ˜

  • BFS๋กœ ํ•˜๋‚˜์”ฉ ์ฐพ์•„๊ฐˆ ์ˆ˜ ์žˆ์ง€๋งŒ, ๋‚˜๋Š” ์—ฐ๊ฒฐ๋˜์–ด์žˆ๋Š” ํƒ€์ผ์„ ๊ทธ๋ž˜ํ”„๋กœ ํ‘œํ˜„ํ•œ ๋‹ค์Œ BFS๋ฅผ ํ•˜์˜€๋‹ค.
  • BFS๋ฅผ ํ• ๋•, visit์„ -1๋กœ ์ดˆ๊ธฐํ™”ํ•˜๊ณ , ์ด์ „์— ์˜จ ๊ณณ์„ ๊ธฐ๋กํ•˜๋Š” ํ˜•์‹์œผ๋กœ ํ•˜์ž.
    • ๊ทธ๋Ÿฌ๋ฉด ๋งˆ์ง€๋ง‰์—์„œ๋ถ€ํ„ฐ ์˜จ๊ณณ์„ ํƒ์ƒ‰ํ•˜๋ฉฐ ๊ฐ€์„œ ์ฒซ๋ฒˆ์งธ ํƒ€์ผ๊นŒ์ง€ ๊ฐ€๋ฉด ๋œ๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
using namespace std;
 
int N, tile[250000][2], last, visit[250000];
vector<int> graph[250000], path;
list<int> l;
 
void makeGraph();
void bfs();
 
int main() {
	cin >> N;
	last = N * N - N / 2;
	for (int i = 1; i <= last; i++)
		cin >> tile[i][0] >> tile[i][1];
 
	makeGraph();
 
	memset(visit, -1, sizeof(visit));
	bfs();
 
	cout << path.size() << endl;
	for (int j = path.size() -1; j >=0; j--)
		cout << path[j] << " ";
}
 
void makeGraph() {
	for (int i = 1; i <= N; i++) {
		int end, start;
		if (i % 2 == 0) {	// ์ง์ˆ˜์ค„
			end = N - 1;
			start = N * (i / 2) + (N - 1) * ((i / 2) - 1);
		}
		else {	// ํ™€์ˆ˜์ค„
			end = N;
			start = N * (i / 2) + (N - 1) * (i / 2);
		}
 
		// ์ขŒ์šฐ, +-N, +-(N-1), ์ด๋•Œ ํ™€์ˆ˜๋ฒˆ์งธ ์ฒ˜์Œ์€ +N-1, -N ์•ˆ๋˜๊ณ , ๋งˆ์ง€๋ง‰์€ +N, -N-1 ์•ˆ๋จ
		for (int j = start + 1; j <= start + end; j++) {
			if (j != start + 1 || i % 2 == 0) {	// ์™ผ์ชฝ
				if (tile[j - 1][1] == tile[j][0] && j != start + 1)
					graph[j].push_back(j - 1);
				if (j - N >= 1 && tile[j - N][1] == tile[j][0])	// -N
					graph[j].push_back(j - N);
				if (j + N - 1 <= last && tile[j + N - 1][1] == tile[j][0]) 	// +N-1
					graph[j].push_back(j + N - 1);
			}
			if (j != start + end || i % 2 == 0) { // ์˜ค๋ฅธ์ชฝ
				if (tile[j + 1][0] == tile[j][1] && j != start + end)
					graph[j].push_back(j + 1);
				if (j - N + 1 >= 1 && tile[j - N + 1][0] == tile[j][1]) // -(n-1)
					graph[j].push_back(j - N + 1);
				if (j + N <= last && tile[j + N][0] == tile[j][1])  // + N
					graph[j].push_back(j + N);
			}
		}
	}
}
// ๋‹ค์ต์ŠคํŠธ๋ผ ํ›„ ๊ฒ€์ฆ์œผ๋กœ ๊ธธ์ฐพ๊ธฐ
void bfs() {
	visit[1] = 0;
	l.push_back(1);
	while (!l.empty()) {
		int cur = l.front();
		l.pop_front();
 
		for (int i = 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i];
			if (visit[next] == -1) {
				visit[next] = cur;
				l.push_back(next);
			}
		}
	}
 
	int first = 0;
	for (int i = last; i >= 1; i--) {
		if (visit[i] != -1) {
			first = visit[i];
			path.push_back(i);
			break;
		}
	}
 
	int cur = first;
	while (cur != 0) {
		path.push_back(cur);
		cur = visit[cur];
	}
	return;
}