์๊ณ ๋ฆฌ์ฆ
- 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;
}